Cook–Levin theorem
The theorem is named after Stephen Cook and Leonid Levin.
[1] An important consequence of this theorem is that if there exists a deterministic polynomial-time algorithm for solving Boolean satisfiability, then every NP problem can be solved by a deterministic polynomial-time algorithm.
The question of whether such an algorithm for Boolean satisfiability exists is thus equivalent to the P versus NP problem, which is still widely considered the most important unsolved problem in theoretical computer science.
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"[2] in conference proceedings of the newly founded ACM Symposium on Theory of Computing.
Richard Karp's subsequent paper, "Reducibility among combinatorial problems",[1] generated renewed interest in Cook's paper by providing a 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.
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 NPA is not a subset of TA.
[3] In the USSR, a result equivalent to Baker, Gill, and Solovay's was published in 1969 by M.
[4] Later Leonid Levin's paper, "Universal search problems",[5] 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 problems, which require finding solutions rather than simply determining existence.
A decision problem is in NP if it can be decided by a non-deterministic Turing machine in polynomial time.
Given any decision problem in NP, construct a non-deterministic machine that solves it in polynomial time.
Then the expression can be satisfied if and only if there is a way for the machine to run correctly and answer "yes", so the satisfiability of the constructed expression is equivalent to asking whether or not the machine will answer "yes".
There are two parts to proving that the Boolean satisfiability problem (SAT) is NP-complete.
SAT is in NP because any assignment of Boolean values to Boolean variables that is claimed to satisfy the given expression can be verified in polynomial time by a deterministic Turing machine.
(The statements verifiable in polynomial time by a deterministic Turing machine and solvable in polynomial time by a non-deterministic Turing machine are equivalent, and the proof can be found in many textbooks, for example Sipser's Introduction to the Theory of Computation, section 7.3., as well as in the Wikipedia article on NP).
Now suppose that a given problem in NP can be solved by the nondeterministic Turing machine
is known, witnessing the membership of the given problem in NP, the transformation cannot be effectively computed, unless an upper bound
While the above method encodes a non-deterministic Turing machine in complexity
[8][9][10][11][12] The quasilinear result first appeared seven years after Cook's original publication.
The QBF problem can be used to encode computation with a Turing machine limited to polynomial space complexity, proving that there exists a problem (the recognition of true quantified Boolean formulas) that is PSPACE-complete.
Analogously, dependency quantified boolean formulas encode computation with a Turing machine limited to logarithmic space complexity, proving that there exists a problem that is NL-complete.
[13][14] The proof shows that every problem in NP can be reduced in polynomial time (in fact, logarithmic space suffices) to an instance of the Boolean satisfiability problem.
This means that if the Boolean satisfiability problem could be solved in polynomial time by a deterministic Turing machine, then all problems in NP could be solved in polynomial time, and so the complexity class NP would be equal to the complexity class P. The significance of NP-completeness was made clear by the publication in 1972 of Richard Karp's landmark paper, "Reducibility among combinatorial problems", in which he showed that 21 diverse combinatorial and graph theoretical problems, each infamous for its intractability, are NP-complete.
For example, he showed the problem 3SAT (the Boolean satisfiability problem for expressions in conjunctive normal form (CNF) with exactly three variables or negations of variables per clause) to be NP-complete by showing how to reduce (in polynomial time) any instance of SAT to an equivalent instance of 3SAT.
[15] Garey and Johnson presented more than 300 NP-complete problems in their book Computers and Intractability: A Guide to the Theory of NP-Completeness,[16] and new problems are still being discovered to be within that complexity class.
Although many practical instances of SAT can be solved by heuristic methods, the question of whether there is a deterministic polynomial-time algorithm for SAT (and consequently all other NP-complete problems) is still a famous unsolved problem, despite decades of intense effort by complexity theorists, mathematical logicians, and others.
