Masalah P versus NP

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.