P vs NP

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   untuk suatu a bilangan bulat positif, berapa a? nah..itu ada rumusan sendiri untuk mencarinya, saya tidak akan membahasnya. Nah rumusan waktu tersebut dikatakan polynomial time (waktu polynomial)

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

———————————————————————————————————————————————-

**Ingin mendapatkan kaos unik bertema matematika silahkan kunjungi kaos.ariaturns.com**