Editing Cook–Levin theorem (section)

==Contributions==
The concept of [[NP-completeness]] was developed in the late 1960s and early 1970s in parallel by researchers in North America and the [[Soviet Union]].
In 1971, [[Stephen Cook]] published his paper "The complexity of theorem proving procedures"<ref>{{cite book|title=Proceedings of the Third Annual ACM Symposium on Theory of Computing|last=Cook|first=Stephen|year=1971|pages=151–158|chapter=The complexity of theorem proving procedures|doi=10.1145/800157.805047|isbn=9781450374644|s2cid=7573663|author-link=Stephen Cook|chapter-url=http://portal.acm.org/citation.cfm?coll=GUIDE&dl=GUIDE&id=805047}}</ref> in conference proceedings of the newly founded ACM [[Symposium on Theory of Computing]]. [[Richard Karp]]'s subsequent paper, "Reducibility among
combinatorial problems",<ref name="Karp"/> generated renewed interest in Cook's paper by providing a [[Karp's 21 NP-complete problems|list of 21 NP-complete problems]]. Karp also introduced the notion of completeness used in the current definition of NP-completeness (i.e., by [[polynomial-time many-one reduction]]). Cook and Karp each received a [[Turing Award]] for this work.

<!--
THIS IS POORLY WORDED:

Another important contribution of Karp was to notice
that many NP-complete problems, while seemingly intractable in the
worst case, are actually easy for almost all random instances.{{Citation needed|date=March 2008}} In 1984, Levin
extended this result by proving that some NP problems
are complete in the average case as well.<ref>http://www.claymath.org/millennium/P_vs_NP/pvsnp.pdf {{Dead link|date=February 2022}}</ref>

-->
The theoretical interest in NP-completeness was also enhanced by the work of Theodore P. Baker, John Gill, and [[Robert Solovay]] who showed, in 1975, that solving NP-problems in certain [[oracle machine]] models requires exponential time. That is, there exists an oracle ''A'' such that, for all subexponential deterministic-time complexity classes T, the relativized complexity class NP<sup>''A''</sup> is not a subset of T<sup>''A''</sup>. In particular, for this oracle, P<sup>''A''</sup>&nbsp;≠&nbsp;NP<sup>''A''</sup>.<ref>{{cite journal|author = T. P. Baker|author2=J. Gill |author3=R. Solovay |title = Relativizations of the P = NP question|journal = SIAM Journal on Computing |volume = 4|issue = 4|pages = 431–442|year = 1975|doi = 10.1137/0204037}}</ref>

In the USSR, a result equivalent to Baker, Gill, and Solovay's was published in 1969 by M. Dekhtiar.<ref>{{cite journal|last=Dekhtiar|first=M.|title = On the impossibility of eliminating exhaustive search in computing a function relative to its graph|journal = [[Proceedings of the USSR Academy of Sciences]]|volume = 14|pages = 1146–1148|year = 1969|language=ru}}</ref> Later [[Leonid Levin]]'s paper, "Universal search problems",<ref>{{cite journal|last=Levin|first=Leonid|author-link=Leonid Levin|trans-title = Universal search problems|language=ru|title= Универсальные задачи перебора|journal = Problems of Information Transmission |volume = 9|issue = 3|pages = 115–116|year = 1973|url=http://www.mathnet.ru/eng/ppi914}} Translated into English by {{cite journal|last=Trakhtenbrot|first=B. A.|author-link=Boris Trakhtenbrot | title = A survey of Russian approaches to ''perebor'' (brute-force searches) algorithms|journal = [[Annals of the History of Computing]] |volume = 6|issue = 4|pages = 384–400|year = 1984|doi=10.1109/MAHC.1984.10036|s2cid=950581}} Translation see appendix, p.399-400.</ref> was published in 1973, although it was mentioned in talks and submitted for publication a few years earlier.

Levin's approach was slightly different from Cook's and Karp's in that he considered [[search problem]]s, which require finding solutions rather than simply determining existence. He provided six such NP-complete search problems, or ''universal problems''.
Additionally he found for each of these problems an algorithm that solves it in optimal time (in particular, these algorithms run in polynomial time if and only if [[P versus NP problem|P = NP]]).