Problem P vs NP, Masalah yang Tak Mudah Dilakukan Komputer, namun Mudah...

Problem P vs NP, Masalah yang Tak Mudah Dilakukan Komputer, namun Mudah untuk Diperiksa

7 Millenium Problems

Ilustrasi / ist

SHNet, Peterborough -Satu lagi soal yang belum terpecahkan dalam 7 Millenium Problems yang dikemukakan Clay Mathematics Institute adalah solusi dari masalah P vs NP. Isu yang mendasari masalah ini pertama kali dibahas pada tahun 1950-an, dalam sebuah surat dari John Forbes Nash Jr. ke National Security Agency, dan surat Kurt Gödel ke John von Neumann. Sama dengan enam masalah utama lainnya, pemecahan soal P vs NP juga diberikan hadiah senilai US $ 1.000.000 bagi pencetus solusi pertama yang benar.

Pernyataan terperinci masalah P versus NP diperkenalkan pada tahun 1971 oleh Stephen Cook dalam makalah seminarnya “Kompleksitas prosedur pembuktian teorema” dan dianggap oleh banyak orang sebagai masalah terbuka terpenting dalam bidang ilmu komputer.

Baca juga:

P (mudah ditemukan) Vs NP (mudah diperiksa) adalah masalah yang belum terpecahkan di dunia ilmu komputer teoritis. Secara sederhana, masalahnya pada dasarnya menanyakan hal ini: jika mudah untuk memastikan bahwa solusi atas sebuah masalah sudah benar, apakah ini juga mudah untuk memecahkan masalah?

“P” di sini adalah singkatan dari waktu polinomial, yaitu masalah yang lebih mudah dipecahkan oleh komputer dan “NP” adalah singkatan dari waktu polinomial nondeterministik, yaitu masalah yang tidak mudah dilakukan komputer, namun mudah untuk diperiksa. Salah satu contohnya adalah menemukan faktor utama bilangan besar.

Jika Anda memiliki semua daftar faktor yang mungkin, Anda dapat dengan mudah memperbanyaknya bersama-sama dan memeriksa apakah Anda bisa mendapatkan kembali nomor aslinya. Namun, tidak ada cara yang mungkin untuk menemukan faktor jumlah itu. Matematikawan percaya bahwa tidak ada bukti yang memungkinkan hal itu terjadi, namun membuktikan hal yang sama itu sendiri adalah tugas yang menakutkan dan karena itu tetap merupakan salah satu Masalah Milenium yang belum terpecahkan. Masalahnya diformulasikan oleh Stephen Cook dan Leonid Levin pada tahun 1971. (GP)