Hadiah 1 juta US$ dari Clay Mathematics Institute

Rumus P=NP adalah salah satu pertanyaan terbuka yang paling terkenal dalam bidang teori komputasi dan matematika. Mari kita bahas kedua istilah yang terlibat dalam rumus ini.

Definisi

1. P (Polynomial Time):

Kelas masalah yang dapat diselesaikan oleh algoritma dalam waktu polinomial, yaitu waktu penyelesaian algoritma dapat dinyatakan sebagai polinomial dari ukuran input (n). Masalah-masalah ini dianggap "mudah" atau "cepat" untuk diselesaikan.

Contoh masalah dalam kelas P termasuk pengurutan, pencarian, dan aritmetika dasar.

2. NP (Nondeterministic Polynomial Time):

Kelas masalah untuk yang solusinya dapat diverifikasi dalam waktu polinomial, meskipun kita tidak tahu bagaimana cara menemukan solusi tersebut dengan cepat. Dalam konteks ini, "nondeterministic" berarti bahwa jika kita memiliki kandidat solusi, kita dapat memeriksa keabsahannya dengan cepat.

Contoh masalah NP termasuk masalah knapsack, graf bipartit, dan pemisahan graf.

P=NP?

Ketika kita mengatakan P=NP, itu berarti bahwa setiap masalah yang dapat diverifikasi dalam waktu polinomial (NP) juga dapat diselesaikan dalam waktu polinomial (P).

Jika P=NP, banyak masalah yang saat ini dianggap sulit untuk diselesaikan akan memiliki solusi yang dapat ditemukan dengan cepat.

Sebaliknya, jika P≠NP, maka ada masalah yang sulit untuk diselesaikan meskipun kita dapat memverifikasi solusinya dengan cepat.

Implikasi

Jika P=NP, banyak algoritma dan sistem yang kita gunakan dalam kriptografi, optimisasi, dan teori graf akan perlu dipertimbangkan kembali, karena banyak dari metode keamanan saat ini bergantung pada asumsi bahwa beberapa masalah tidak dapat diselesaikan dengan cepat.

Sebaliknya, jika P≠NP, ini akan mengkonfirmasi batasan fundamental pada apa yang dapat dilakukan oleh algoritma dalam komputasi.

Kesimpulan

Pertanyaan tentang P=NP belum terjawab dan merupakan salah satu dari tujuh "Masalah Milenium" yang ditetapkan oleh Clay Mathematics Institute, dengan hadiah satu juta dolar untuk bukti yang tepat. Penemuan dalam area ini bisa merevolusi ilmu komputer dan banyak disiplin ilmu lainnya.