Editing P versus NP problem (section)

==History==

The precise statement of the P versus NP problem was introduced in 1971 by [[Stephen Cook]] in his seminal paper "The complexity of theorem proving procedures"<ref>{{Cite book|last=Cook|first=Stephen|author-link=Stephen Cook|year=1971|chapter=The complexity of theorem proving procedures|chapter-url=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|doi=10.1145/800157.805047|isbn=9781450374644|s2cid=7573663}}</ref> (and independently by [[Leonid Levin]] in 1973<ref>{{cite journal |author=L. A. Levin |url=http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=ppi&paperid=914&option_lang=rus |script-title=ru:Универсальные задачи перебора |trans-title=Problems of Information Transmission |journal=Пробл. передачи информ |date=1973 |volume=9 |number=3 |pages=115–116 |language=ru}}</ref>).

Although the P versus NP problem was formally defined in 1971, there were previous inklings of the problems involved, the difficulty of proof, and the potential consequences. In 1955, mathematician [[John Forbes Nash Jr.|John Nash]] wrote a letter to the [[National Security Agency|NSA]], speculating that cracking a sufficiently complex code would require time exponential in the length of the key.<ref>{{cite web |title=Letters from John Nash |url=https://www.nsa.gov/Portals/70/documents/news-features/declassified-documents/nash-letters/nash_letters1.pdf |archive-url=https://web.archive.org/web/20181109234811/https://www.nsa.gov/Portals/70/documents/news-features/declassified-documents/nash-letters/nash_letters1.pdf |archive-date=2018-11-09 |url-status=live |author=NSA |year=2012}}</ref> If proved (and Nash was suitably skeptical), this would imply what is now called P&nbsp;≠&nbsp;NP, since a proposed key can be verified in polynomial time. Another mention of the underlying problem occurred in a 1956 letter written by [[Kurt Gödel]] to [[John von Neumann]]. Gödel asked whether theorem-proving (now known to be [[co-NP-complete]]) could be solved in [[quadratic time|quadratic]] or [[linear time]],<ref>{{cite journal | last1 = Hartmanis | first1 = Juris | title = Gödel, von Neumann, and the P = NP problem | url = http://ecommons.library.cornell.edu/bitstream/1813/6910/1/89-994.pdf | journal = Bulletin of the European Association for Theoretical Computer Science | volume = 38 | pages = 101–107 }}</ref> and pointed out one of the most important consequences&mdash;that if so, then the discovery of mathematical proofs could be automated.