Masalah P versus NP: Perbedaan antara revisi

 

 

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"<ref>{{Cite book|last=Cook|first=Stephen|authorlink=Stephen Cook|year=1971|chapter=The complexity of theorem proving procedures|chapterurl=http://portal.acm.org/citation.cfm?coll=GUIDE&dl=GUIDE&id=805047|title=Proceedings of the Third Annual ACM Symposium on Theory of Computing|pages=151–158}}</ref> dan dianggap oleh banyak orang sebagai masalah terbuka terpenting dalam bidang [[ilmu komputer]].<ref>{{cite journal | last1 = Fortnow | first1 = Lance | authorlink = Lance Fortnow | year = 2009 | title = The status of the '''P''' versus '''NP''' problem | url = http://www.cs.uchicago.edu/~fortnow/papers/pnp-cacm.pdf | format = PDF | journal = Communications of the ACM | volume = 52 | issue = 9| pages = 78–86 | doi = 10.1145/1562164.1562186 }}</ref> 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.