Cook–Levin theorem

In computational complexity theory, Cook's theorem, proved by Stephen Cook in his 1971 paper "The Complexity of Theorem Proving Procedures", states that the Boolean satisfiability problem is NP-complete.

The theorem was independently proved by Leonid Levin at about the same time; it is sometimes called the Cook–Levin theorem.

Definitions

A decision problem is in NP if a non-deterministic Turing machine can verify an answer of the decision problem in polynomial time.

A decision problem is NP-complete if it is in NP and if every problem in NP can be reduced to it by a polynomial-time many-one reduction.

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

Proof

The Boolean satisfiability problem is in NP because a non-deterministic Turing machine can guess an assignment of truth values to the variables, determine the value of the expression under that assignment, and accept if the assignment makes the entire expression true.

Now suppose that a problem in NP is solved by the non-deterministic Turing machine M = (Q, Σ, s, F, δ) (where Q is the set of states, Σ the alphabet of tape symbols, s ∈ Q the initial state, F ⊆ Q the set of accepting states, and δ : Q × Σ → Q × Σ × {−1,+1} the set of transitions) and that M accepts or rejects an instance of the problem in time p(n) where n is the size of the instance and p is a polynomial function.

We describe for each instance I a Boolean expression which is satisfiable if and only if the machine M accepts I.

The Boolean expression uses the variables set out in the following table, where q ∈ Q, −p(n) ≤ i ≤ p(n), j ∈ Σ, and 0 ≤ k ≤ p(n):

Variables	Intended interpretation	How many?
Tijk	True if tape cell i contains symbol j at step k of the computation.	O(p(n)²)
Hik	True if the M's read/write head is at tape cell i at step k of the computation.	O(p(n)²)
Qqk	True if M is in state q at step k of the computation.	O(p(n))

Define the Boolean expression B to be the conjunction of the clauses in the following table, for all −p(n) ≤ i ≤ p(n) and 0 ≤ k ≤ p(n):

Clauses	Conditions	Interpretation	How many?
Tij0	Tape cell i of the input I contains symbol j.	Initial contents of the tape.	O(p(n))
Qs0		Initial state of M	O(1)
H00		Initial position of read/write head.	O(1)
Tijk → ¬ Tij′k	j ≠ j′	One symbol per tape cell.	O(p(n)²)
Tijk = Tij(k+1) ∨ Hik		Tape remains unchanged unless written.	O(p(n)²)
Qqk → ¬ Qq′k	q ≠ q′	Only one state at a time.	O(p(n))
Hik → ¬ Hi′k	i ≠ i′	Only one head position at a time.	O(p(n)²)
The disjunction of the clauses (Hik ∧ Qqk ∧ Tiσk) → (H(i+d)(k+1) ∧ Qq′(k+1) ∧ Tiσ′(k+1))	(q, σ, q′, σ′, d) ∈ δ	Possible transitions at computation step k when head is at position i.	O(p(n)²)
The disjunction of the clauses Qf(p(n))	f ∈ F.	Must finish in an accepting state.	O(1)

If there is an accepting computation for M on input I, then B is satisfiable, by assigning T_ijk, H_ik and Q_ik their intended interpretations. On the other hand, if B is satisfiable, then there is an accepting computation for M on input I that follows the steps indicated by the assignments to the variables.

How large is B? There are O(p(n)²) Boolean variables, each of which may be encoded in space O(log p(n)). The number of clauses is O(p(n)²). So the size of B is O((log p(n)) p(n)²). This is polynomial in n, the size of the input, so the transformation is certainly a polynomial-time many-one reduction, as required.

Consequences

The proof shows that any 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.

Cook's theorem was the first proof of NP-completeness for any problem. Other proofs of NP-completeness generally proceed by reducing the problem from another problem that has already been shown to be NP-complete. For example, the problem 3-SAT (the satisfiability problem for Boolean expressions in conjunctive normal form with three variables or negations of variables per clause) can be shown to be NP-complete by showing how to reduce any instance of SAT to an equivalent instance of 3-SAT.

Garey and Johnson present 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.