Cook's 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.
| Contents |
Definitions
A decision problem is in NP if a non-deterministic Turing machine can solve it 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 iff tape cell i contains symbol j at step k of the computation. | O(p(n)²) |
| Hik | True iff the M's read/write head is at tape cell i at step k of the computation. | O(p(n)²) |
| Qqk | True iff 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 Tijk, Hik and Qik 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
We have shown that any problem in NP can be reduced in polynomial time 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 to 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 added to the complexity class.
References
- Michael R. Garey and David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, 1979.de:Satz von Cook