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 n^a+a  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 n^a+a

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)

travelling-salesmanBayangkan 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 P\subset NP

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**

Advertisements

About Aria Turns

Seorang Alumnus Matematika UGM, dengan ilmu yang didapat ketika kuliah (Padahal sering bolos kuliah :p ), saya menyebarkan virus matematika
This entry was posted in millennium problem and tagged , , , , . Bookmark the permalink.

7 Responses to P vs NP

  1. eka says:

    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

  2. kauleea says:

    wah makasih neh dapet pencerahan buat UAS besok,,,abiz bingung masalah NP,,sayangnya belum ditambah NP-Complete,,,tapi gpp alhamdulillah lumayan ngerti,,,(^_^)

  3. Novri Suhermi says:

    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…

  4. toocool says:

    terimakasih mas informasinya, sangat berguna..=)
    oia tp ada beberapa kata yang hilang mas..

Silahkan, tinggalkan komentar

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s