Sunday, May 11, 2014

Lecture Note: Apa itu P dan NP problem?



Sewaktu saya pertama kali mengikuti mata kuliah Analisis dan Desain Algoritma saya disuguhkan Big O Notation. Ini adalah notasi untuk menyatakan kompleksitas dari sebuah algoritma dalam memecahkan permasalahan. Ngomongin permasalahan, ada yang manya P dan NP problem. Saya kurang tahu mengenai problem ini, untung saja pak Lala Septem Riza menulis tentang ini di grup jurusan saya. Haha. Berikut tulisan yang beliau buat: 

[LECTURE NOTE] Apa itu P dan NP problem ? apakah P = NP atau P != NP ? pasti pernah mendengar itu kan ? Saya hanya menulis sedikit dari topik itu, tambahan/koreksi lebih diharapkan . Suatu algoritma bisa dimasukkan dalam P problem jika alg itu bisa menyelesaikan (SOLVE) problem secara efisien/polinomial. Sedangkan NP adalah algorithm yang hanya bisa melakukan verifikasi (VERIFY) permasalahan itu secara efisien. Saat ini masalah apakah P = NP atau P != NP masih jadi misteri yang tak terpecahkan di computer science. Jadi jika anda bisa memecahkannya dengan memberikan pembuktian secara matematika maka rekening bank anda pasti dipenuhi dengan jutaan dollar . Apa contoh P dan NP ? Misalkan gini, kalau anda diberi problem perkalian: 131 * 71 = ?, maka komputer anda/anda sendiri dengan kurang dari 1 detik, bisa menjawab 9301, bukan ? Karena complexity dari perkalian hanya O(n^2) (maksimal, krn bisa dibuat kurang dari itu). Itu artinya perkalian adalah P (polynomial) problem. Tapi sekarang kalau diberi soal seperti ini: x * y = 9301, maka algo yang anda buat butuh waktu komputasi yg panjang. Tentu saja untuk kasus ini, anda tahu jawabannya xixixi. Ini hanya kasus sederhana, karena bisa jadi jumlah digitnya bisa puluhan/ratusan dan butuh puluhan/ratusan tahun untuk tahu jawabannya. Inilah yg disebut permasalahan faktorisasi, dan ini digolongkan sebagai NP (nondeterministic polynomial) problem. Tapi sekalinya anda bisa menemukan solusi x dan y, anda gampang untuk memverifikasinya bukan .Permasalahan yang timbul adalah apakah P = NP atau P != NP ? jika anda bisa membuktikan bahwa P = NP itu artinya, apapun masalah yang sulit (tak bs dipecahkan scr efisien) bisa dibuatkan algorithm yang efisien (P). Kalau ini terjadi, maka seluruh bank di dunia ini akan TUTUP karena pembuktian anda . Anda akan dapat turing award (nobelnya di computer). Kenapa begitu ? karena semua bank mengandalkan enkripsi berdasarkan faktorisasi (rsa). Akan tetapi sebaliknya, walaupun secara intuitif P != NP, nyatanya untuk membuktikannya pun juga tidak gampang, bahkan sampai skrgpun belum ada yang bisa. Jadi mangga bagi yang tertarik dapat jutaan dollar .

Demikian tulisan beliau. Btw, di tulisan beliau tersebut ada x*y = 9301. Nah loh, jawabannya apa? Problem ini bisa dipecahkan dengan Linear Diophantine. Tentang Linear Diophantine bisa baca di blognya alijaya di http://alijayameilio.blogspot.com/2012/08/linear-diophantine.html, tutorial yang dia buat enak banget! :D 

UPDATE, linear diophantine kata ali nggak bisa buat perkalian, hehe (baca comment), tapi teteup, postingan dia enak buat dibaca :p

2 comments:

  1. giri... errr... linear diophantine kayaknya cuman dalam bentuk ax + by = c deh ._.
    perkalian kagak isa :v...

    untuk faktorisasi 9301 *which is aku ngamsumsiin x sama y harus integer...

    itu cara paling mudahnya itu ngiterasiin angka dari 1 sampai sqrt(9301) dan ngeliat ada angka yang kalau ngemodulo 9301 itu jadi 0 apa nggak...

    dan sebenernya x sama y itu juga bisa lebih dari satu jawaban, masalahnya jawaban mana yang mau diambil?

    Paling gampang mah x = 1, y = 9301 :v... karena gak ada syarat lain, ini jawaban harusnya betul :v...

    Problem di RSA itu kalau gak salah inget seh sama kayak gini x * y = sesuatu, dimana sesuatunya itu diketahui, dan kita harus cari x sama y nya, dengan syarat, x sama y nya itu bilangan prima *kalau gak salah*.

    Nah kalau pada awalnya x sama y nya itu bilangan prima yang gedenya amit2, kalau dikali jadi gede amit2 juga, kalau dicari lagi awalnya x sama y nya itu yang baru ribet :v... karena kalau nggak salah, kalau perlu diiterasi dari 1 sampai sqrt(sesuatu) itu bakal masih lama :v...

    ReplyDelete
    Replies
    1. Huoo, iya? Waah, baru tahu ternyata gitu ya problemnya, harus di brute force

      update.. update...

      Delete

Comment is caring :)