Kali ini saya mau menuliskan salah satu masalah dari seven melinium problem yaitu P vs NP. Ini adalah masalah termuda dari seven melinium problem, dicetuskan oleh Stephen Cook pada tahun 1971 dan ini adalah masalah didalam Algoritma.
P
Misalkan kita punya masalah menghitung nilai determinan matriks bujur sangkar berukuran n maka dengan program komputer/algoritma dengan mudah kita mengetahui solusinya. Nah..masalah menghitung nilai determinan ini disebut decision problem (masalah yang dapat diputuskan) yaitu masalah yang dapat ditemukan solusinya aloh suatu algoritma . Contoh-contoh decision problem yang lain adalah: mengkonnversi nilai celcius ke fahrenhait, menghitung perkalian dua bua matriks, dll pokoknya banyak lah masalah-masalah yang termasuk decision problem, cari aja sendiri contoh yang lainnya 🙂
Nah..sekarang balik lagi ke masalah penghitungan matriks, kita tau bahwa semakin besar ukuran matriksnya maka semakin lama komputer memproses jawabannya, dengan rumusan waktu proses 
Suatu masalah berukuran n byte dikatakan termuat di kelas P, jika algoritma membutuhkan polynomial time untuk memproses solusnya.atau dengan kata lain suatu masalah berukuran n byte termuat di P jika ada algorima A yang akan memproses solusi paling lama
Pada umumnya masalah-masalah di P mempunyai nilai a paling besar 4, tapi pada kasus ekstrim seperti malah tes keprimaan nilai a sebesar 6
NP
Nah..jika masalah di P, algoritma memproses solusinya tetapi masalah di NP, algoritma hanya mengecek/memverifikasi solusi dengan masalah, apakah cocok/tepat atau tidak. Misakan kita punya suatu masalah NP, jika kita masukan ke algoritma maka algoritma akan mgecek maslah NP tersebut dengan dugaan-dugaan solusi satu persatu, apakah cocok atau tidak.
Contoh masalah NP adalah Traveling salesman Problem (TSP)
Bayangkan kalian akan mengunjungi lima kota untuk keperluan dagang dan kalian semua jarak masing-masing kota, Pertanyaannya jalur mana yamg terpendek untuk mengunjungi semua kota dan kembali lagi ke kota semula? Apakah A-B-C-E-D-A?apakah A-D-E-C-B-A?
Tentu saja untuk mencari solusinya adalah mencoba semua kemungkinan.
Semakin banyak kotanya maka semakin banyak pula kombinasinya. Jadi metode ini memeerlukan “waktu faktorial” t=n!
Misalkan suatu algoritma pada suatu komputer dapat menyelesaikan TSP dengan 20 kota dalam waktu 1 detik maka 21 kota akan diselesaikan dalam waktu 21 detik dan 22 kota dalam waktu 462 detik (sekitar 7menit) kalau 30 kota akan membutuhkan waktu sebanyak 3 milyar tahun, wow..
Dari contoh TSP diatas diketahui bahwa untuk memecahkan suatu masalah NP, paertama-tama algoritma akan memproses dugaan solusi kemudian mencocokannya dengan masalah apakah cocok atau tidak kalau cocok maka berhenti kalau tidak cocok maka kembali memproses dugaan solsusi lain dan mencocokannya kembali begitu seterusnya sampai ditemukan solusi yang benar-benar cocok. Jadi masalah NP mememerlukan waktu yang jaug lebih lama untuk memecahkannya dibanding masalah P dan jelas bahwa
Nah..sekarang yang menjadi pertanyaan
Apakah P=NP?
Atau dengan kata lain apakah kita bisa membuat algoritma ber”polynomial time” untuk memecahkan masalah NP? Apakah sebenernya kita bisa membuat algoritma yang memecahkan masalah NP sama cepatnya dengan algoritma untuk memecahkan masalah P?
Banyak orang yang berkeyakinan nahwa P≠NP, tetapi sampai saat ini belum ada yang mampu memebuktikan secara matematis apakah P=NP atau kah P≠NP
Andaikan P=NP
Jika suatu saat terbukti secara matematis bahwa P=NP, maka berakibat semua masalah computable yaitu masalah yang bisa diproses melalaui komputer dengan mudah ditemukan solusinya. Banyak masalah dalam ilmu Riset Operasi yang termasuk NP, jika P=NP maka ilmu riset operasi akan melompat jauh kedepan ini berakibat semua proses Industri di segala bidang akan bekerja jauh lebih efisien. Tapi P=NP merupakan mimpi buruk bagi ilmu kriptografi karna itu artinya akan ada metode lain yang jauh lebih cepat, lebih efisien untuk memecahkan suatu enkripsi selain brute force
Blog Matematika Pak Satria 
mas mau nanya nih, kalo misalkan saya mau mengubah derajat celcius ke kelvin maka saya akan menggunakan rumus N + 273 kan??
trus menurut anda bener ngak kalo misalkan masalah TSP itu diselesaikan dengan penambahan jarak yang ditempuh oleh motor tersebut misalkan ada 5 kota dengan jarak jarak yang dah diketahui, misal a-b 1 b-c 2 c-d 3 d-e 4 a-e 5
nah jika seperti itu maka peluangnya ada? 1+2+3+4+5 atau 1+2+3+4+3+2+1, dari sini komputer lalu mengecek value terkecil, lah kalo seperti itu maka sama kan? kita tinggal membuat program dengan kemampuan untuk menghitung lajur yang saling berhubungan. jadi kesimpulannya kita hanya perlu menciptakan sebuah rumusan baru untuk setiap program yang berbeda, P vs NP adalah sama kita menggunakan kemampuan algoritma untuk mencari kemungkinan karena kita belum mampu menciptakan algoritma untuk program tersebut, mas gimana pendapat saya?? ada bantahan? maaf hanya berpendapat
itu kamu brute force, jadi masuk ke NP..
wah makasih neh dapet pencerahan buat UAS besok,,,abiz bingung masalah NP,,sayangnya belum ditambah NP-Complete,,,tapi gpp alhamdulillah lumayan ngerti,,,(^_^)
Mas, bahas tentang semua soal seven millenium problem itu donk…
yang udah dibahas cuma 2 kan? tentang Hipotesis Riemann ama P vs NP.
Masih ada lagi tentang conjecture poincare, dll. Saya tunggu lho…
terimakasih mas informasinya, sangat berguna..=)
oia tp ada beberapa kata yang hilang mas..
kata yang hilang dimananya yach?
Mungkin di sini:
“Nah..jika masalah di P, algoritma memproses solusinya tetapi masalah di NP, …”