Masalah P versus NP

Masalah P versus NP adalah permasalahan besar yang merupakan salah satu masalah yang belum terpecahkan dalam bidang ilmu komputer. Problema ini menanyakan apakah setiap masalah yang solusinya dapat segera diverifikasi (secara teknis, diverifikasi dalam waktu polinomial) juga dapat dipecahkan dengan cepat (sekali lagi, dalam waktu polinomial).

Isu yang mendasari masalah ini pertama kali dibahas pada tahun 1950-an, dalam surat dari John Forbes Nash Jr. ke National Security Agency, dan dari Kurt Gödel ke John von Neumann. Pernyataan terperinci masalah P versus NP diperkenalkan pada tahun 1971 oleh Stephen Cook dalam paper seminarnya "Kompleksitas prosedur pembuktian teorema" dan dianggap oleh banyak orang sebagai masalah terbuka terpenting dalam bidang ilmu komputer. Problema ini adalah salah satu dari tujuh Masalah Milenium yang dipilih Clay Mathematics Institute untuk membawa hadiah senilai US $ 1.000.000 bagi pencetus solusi pertama yang benar.

Istilah informal dengan cepat, yang digunakan di atas, berarti adanya algoritme yang memecahkan tugas yang berjalan dalam waktu polinom, sehingga waktu untuk menyelesaikan tugas bervariasi sebagai fungsi polinom pada ukuran input ke algoritme (berlawanan dengan, katakanlah, waktu eksponensial). Kelas umum pertanyaan yang beberapa algoritmanya dapat memberikan jawaban dalam waktu polinomial disebut "kelas P" atau hanya "P". Untuk beberapa pertanyaan, tidak ada cara yang diketahui untuk menemukan jawaban dengan cepat, tetapi jika ada informasi yang menunjukkan jawabannya, mungkin untuk memverifikasi jawabannya dengan cepat. Kelas pertanyaan yang jawabannya dapat  diverifikasi  dalam waktu polinom disebut NP, yang berarti "waktu polinomial nondeterministik".

Referensi 

Konjektur
Masalah Milenium
Masalah matematika yang belum terpecahkan
Masalah ilmu komputer yang belum terpecahkan
Optimisasi matematika
Pengenalan yang terkait dengan komputer pada 1956
Teori kompleksitas struktural