Cook–Levin theorem

Definitions

A decision problem is in NP if it can be decided by a nondeterministic Turing machine in polynomial time.

An instance of the Boolean satisfiability problem is a Boolean expression that combines Boolean variables using Boolean operators. Such an expression is satisfiable if there is some assignment of truth values to the variables that makes the entire expression true.

Idea

Given any decision problem in NP, construct a non-deterministic machine that solves it in polynomial time. Then for each input to that machine, build a Boolean expression that computes whether when that specific input is passed to the machine, the machine runs correctly, and the machine halts and answers "yes". 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".

Proof

This proof is based on the one given by Garey & Johnson (1979).

There are two parts to proving that the Boolean satisfiability problem (SAT) is NP-complete. One is to show that SAT is an NP problem. The other is to show that every NP problem can be reduced to an instance of a SAT problem by a polynomial-time many-one reduction.

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 Michael 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 ${\displaystyle M=(Q,\mathrm{\Sigma },s,F,\delta )}$, where ${\displaystyle Q}$ is the set of states, ${\displaystyle \mathrm{\Sigma }}$ is the alphabet of tape symbols, ${\displaystyle s\in Q}$ is the initial state, ${\displaystyle F\subseteq Q}$ is the set of accepting states, and ${\displaystyle \delta \subseteq ((Q\setminus F)\times \mathrm{\Sigma })\times (Q\times \mathrm{\Sigma }\times \{-1,+1\})}$ is the transition relation. Suppose further that ${\displaystyle M}$ accepts or rejects an instance of the problem after at most ${\displaystyle p(n)}$ computation steps, where ${\displaystyle n}$ is the size of the instance and ${\displaystyle p}$ is a polynomial function.

For each input, ${\displaystyle I}$, specify a Boolean expression ${\displaystyle B}$ that is satisfiable if and only if the machine ${\displaystyle M}$ accepts ${\displaystyle I}$.

The Boolean expression uses the variables set out in the following table. Here, ${\displaystyle q\in Q}$ is a machine state, ${\displaystyle -p(n)\le i\le p(n)}$ is a tape position, ${\displaystyle j\in \mathrm{\Sigma }}$ is a tape symbol, and ${\displaystyle 0\le k\le p(n)}$ is the number of a computation step.

Define the Boolean expression ${\displaystyle B}$ to be the conjunction of the sub-expressions in the following table, for all ${\displaystyle -p(n)\le i\le p(n)}$ and ${\displaystyle 0\le k\le p(n)}$:

If there is an accepting computation for ${\displaystyle M}$ on input ${\displaystyle I}$, then ${\displaystyle B}$ is satisfiable by assigning ${\displaystyle T_{i,j,k}}$, ${\displaystyle H_{i,k}}$ and ${\displaystyle Q_{i,k}}$ their intended interpretations. On the other hand, if ${\displaystyle B}$ is satisfiable, then there is an accepting computation for ${\displaystyle M}$ on input ${\displaystyle I}$ that follows the steps indicated by the assignments to the variables.

There are ${\displaystyle O(p(n{)}^2)}$ Boolean variables, each encodable in space ${\displaystyle O(\log p(n))}$. The number of clauses is ${\displaystyle O(p(n{)}^3)}$ so the size of ${\displaystyle B}$ is ${\displaystyle O(\log (p(n))p(n{)}^3)}$. Thus the transformation is certainly a polynomial-time many-one reduction, as required.

Only the first table row (${\displaystyle T_{i,j,0}}$) actually depends on the input string ${\displaystyle I}$. The remaining lines depend only on the input length ${\displaystyle n}$ and on the machine ${\displaystyle M}$; they formalize a generic computation of ${\displaystyle M}$ for up to ${\displaystyle p(n)}$ steps.

The transformation makes extensive use of the polynomial ${\displaystyle p(n)}$. As a consequence, the above proof is not constructive: even if ${\displaystyle M}$ is known, witnessing the membership of the given problem in NP, the transformation cannot be effectively computed, unless an upper bound ${\displaystyle p(n)}$ of ${\displaystyle M}$'s time complexity is also known.

Complexity

While the above method encodes a non-deterministic Turing machine in complexity ${\displaystyle O(\log (p(n))p(n{)}^3)}$, the literature describes more sophisticated approaches in complexity ${\displaystyle O(p(n)\log (p(n)))}$. The quasilinear result first appeared seven years after Cook's original publication.

The use of SAT to prove the existence of an NP-complete problem can be extended to other computational problems in logic, and to completeness for other complexity classes. The quantified Boolean formula problem (QBF) involves Boolean formulas extended to include nested universal quantifiers and existential quantifiers for its variables. 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.

Consequences

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.

Karp showed each of his problems to be NP-complete by reducing another problem (already shown to be NP-complete) to that problem. 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.

Garey and Johnson presented more than 300 NP-complete problems in their book Computers and Intractability: A Guide to the Theory of NP-Completeness, 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. For more details, see the article P versus NP problem.