COOK–LEVIN THEOREM

(Redirected from Cook\'s theorem)
In computational complexity theory, the 'Cook–Levin theorem' (also known as 'Cook's theorem') states that the Boolean satisfiability problem is NP-complete. That is, any problem that can be solved in polynomial time by a nondeterministic Turing machine can be reduced (in polynomial time) to the problem of determining if a Boolean formula is satisfiable.
An important consequence of the theorem is that if we had a polynomial time algorithm for Boolean satisfiability then we would have a polynomial time algorithm for solving ''any'' problem in NP.
The theorem was proved independently by Stephen Cook in his 1971 paper "The Complexity of Theorem Proving Procedures",^[1] and by Leonid Levin in his 1972 paper "Universal Search Problems".^[2] Cook received the Turing Award in 1982 for this work.

Contents

Definitions

Proof

Consequences

References

Definitions

A decision problem is in NP if it can be solved by a non-deterministic algorithm 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

This proof is based on the one given by Garey and Johnson.^[3]
The Boolean satisfiability problem is in NP because a non-deterministic Turing machine in polynomial time 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.
For each input ''I'' we specify 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'' = ''T''''ij''(''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) ∧ ''Q''''q′''(''k''+1) ∧ ''T''''iσ′''(''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 ''Q''''f''(''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.
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.^[4]
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 3-SAT (the satisfiability problem for Boolean expressions in conjunctive normal form 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 3-SAT. (First you use De Morgan's laws to get the formula into conjunctive normal form, then you introduce new variables to split clauses with more than 3 atoms, since (A ∨ B ∨ C ∨ D) ≡ (A ∨ B ∨ Z) ∧ (¬Z ∨ C ∨ D), and you pad out clauses with fewer than 3 atoms with new variables that are guaranteed to be false, since A ≡ (A ∨ Z ∨ Z) ∧ (¬Z ∨ ¬Z ∨ ¬Z).)
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.

References

1. Proceedings of the third annual ACM symposium on Theory of computing, Stephen Cook, , , , 1971,
2. Universal'nye perebornye zadachi, Leonid Levin, , , Problemy Peredachi Informatsii, 1973 English translation, "Universal Search Problems", in A Survey of Russian Approaches to Perebor (Brute-Force Searches) Algorithms, B. A. Trakhtenbrot, , , Annals of the History of Computing, 1984
3. Computers and Intractability: A Guide to the Theory of NP-Completeness, Michael R. Garey and David S. Johnson, , , Freeman, 1979,
4. Complexity of Computer Computations, Richard M. Karp, , , New York: Plenum, 1972,