Cook's theorem
Encyclopedia
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 in NP
can be reduced
in polynomial time by a deterministic Turing machine to the problem of determining whether a Boolean formula is satisfiable.
An important consequence of the theorem is that if there exists a deterministic polynomial time algorithm for solving Boolean satisfiability, then there exists a deterministic polynomial time algorithm for solving all problems in NP
. Crucially, the same follows for any NP complete problem.
The question of whether such an algorithm exists is called the P versus NP problem and it is widely considered the most important unsolved problem in theoretical computer science. The theorem is named after Stephen Cook
and Leonid Levin
.
In the US in 1971, Stephen Cook
published his paper "The complexity of theorem proving procedures" in conference proceedings of the newly-founded ACM Symposium on Theory of Computing
. Richard Karp
's subsequent paper, "Reducibility among
combinatorial problems", generated renewed interest in Cook's paper by providing a list of 21 NP-complete problems
. Cook and Karp 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 that solving NP-problems in Oracle machine
models requires exponential time.
In the USSR, a result equivalent to Baker, Gill, and Solovay's was published in 1969 by M. Dekhtiar. Later Levin
's paper, "Universal search problems", 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 problem
s, which require finding solutions rather than simply determining existence. He provided 6 such NP-complete search problems, or universal problems, and
additionally found that each has an algorithm which solves it in optimal time.
is in NP
if it can be solved by a non-deterministic algorithm in polynomial time.
An instance of the Boolean satisfiability problem is a Boolean expression
that combines Boolean variables using Boolean operator
s.
An expression is satisfiable if there is some assignment of truth values to the variables that makes the entire expression true.
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 totally equivalent, and the proof can be found in many textbooks, for example Sipser's Introduction to the Theory of Computation, section 7.3.).
Now suppose that a given problem in NP can be solved by the nondeterministic Turing machine M = (Q, Σ, s, F, δ), where Q is the set of states, Σ is the alphabet of tape symbols, s ∈ Q is the initial state, F ⊆ Q is the set of accepting states, and δ: Q × Σ → Q × Σ × {−1, +1} is the set of transitions. Suppose further 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. Here, q ∈ Q, −p(n) ≤ i ≤ p(n), j ∈ Σ, and 0 ≤ k ≤ p(n).
Define the Boolean expression B to be the conjunction
of the sub-expressions in the following table, for all −p(n) ≤ i ≤ p(n) and 0 ≤ k ≤ p(n):
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.
There are O(p(n)2) Boolean variables, each encodeable in space O(log p(n)). The number of clauses is O(p(n)2) so the size of B is O(log(p(n))p(n)2). Thus the transformation is certainly a polynomial-time many-one reduction, as required.
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
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. (First you modify the proof of the Cook-Levin theorem, so that the resulting formula is in conjunctive normal form, then you introduce new variables to split clauses with more than 3 atoms. For example, the clause (A ∨ B ∨ C ∨ D) can be replaced by the conjunction of clauses (A ∨ B ∨ Z) ∧ (¬Z ∨ C ∨ D), where Z is a new variable which will not be used anywhere else in the expression. Clauses with fewer than 3 atoms can be padded; for example, A can be replaced by (A ∨ A ∨ A), and (A ∨ B) can be replaced by (A ∨ B ∨ B) ).
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=NP problem.
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
, the Cook–Levin theorem, also known as Cook's theorem, states that the Boolean satisfiability problem
Boolean satisfiability problem
In computer science, satisfiability is the problem of determining if the variables of a given Boolean formula can be assigned in such a way as to make the formula evaluate to TRUE...
is NP-complete. That is, any problem in NP
NP (complexity)
In computational complexity theory, NP is one of the most fundamental complexity classes.The abbreviation NP refers to "nondeterministic polynomial time."...
can be reduced
Reduction (complexity)
In computability theory and computational complexity theory, a reduction is a transformation of one problem into another problem. Depending on the transformation used this can be used to define complexity classes on a set of problems....
in polynomial time by a deterministic Turing machine to the problem of determining whether a Boolean formula is satisfiable.
An important consequence of the theorem is that if there exists a deterministic polynomial time algorithm for solving Boolean satisfiability, then there exists a deterministic polynomial time algorithm for solving all problems in NP
NP (complexity)
In computational complexity theory, NP is one of the most fundamental complexity classes.The abbreviation NP refers to "nondeterministic polynomial time."...
. Crucially, the same follows for any NP complete problem.
The question of whether such an algorithm exists is called the P versus NP problem and it is widely considered the most important unsolved problem in theoretical computer science. The theorem is named after Stephen Cook
Stephen Cook
Stephen Arthur Cook is a renowned American-Canadian computer scientist and mathematician who has made major contributions to the fields of complexity theory and proof complexity...
and Leonid Levin
Leonid Levin
-External links:* at Boston University....
.
Contributions
The concept of NP-completeness was developed in the late 1960s and early 1970s in parallel by researchers in the US and the USSR.In the US in 1971, Stephen Cook
Stephen Cook
Stephen Arthur Cook is a renowned American-Canadian computer scientist and mathematician who has made major contributions to the fields of complexity theory and proof complexity...
published his paper "The complexity of theorem proving procedures" in conference proceedings of the newly-founded ACM Symposium on Theory of Computing
Symposium on Theory of Computing
STOC, the Annual ACM Symposium on Theory of Computing is an academic conference in the field of theoretical computer science. STOC has been organized annually since 1969, typically in May or June; the conference is sponsored by the Association for Computer Machinery special interest group SIGACT.As...
. Richard Karp
Richard Karp
Richard Manning Karp is a computer scientist and computational theorist at the University of California, Berkeley, notable for research in the theory of algorithms, for which he received a Turing Award in 1985, The Benjamin Franklin Medal in Computer and Cognitive Science in 2004, and the Kyoto...
's subsequent paper, "Reducibility among
combinatorial problems", generated renewed interest in Cook's paper by providing a list of 21 NP-complete problems
Karp's 21 NP-complete problems
One of the most important results in computational complexity theory was Stephen Cook's 1971 demonstration of the first NP-complete problem, the boolean satisfiability problem...
. Cook and Karp received a Turing Award
Turing Award
The Turing Award, in full The ACM A.M. Turing Award, is an annual award given by the Association for Computing Machinery to "an individual selected for contributions of a technical nature made to the computing community. The contributions should be of lasting and major technical importance to the...
for this work.
The theoretical interest in NP-completeness was also enhanced by the work of Theodore P. Baker, John Gill
John Gill (climber)
John Gill is an American mathematician who has achieved recognition for his rock-climbing. He is considered the Father of Modern Bouldering by many climbers.-Early life and professional career:...
, and Robert Solovay who showed that solving NP-problems in Oracle machine
Oracle machine
In complexity theory and computability theory, an oracle machine is an abstract machine used to study decision problems. It can be visualized as a Turing machine with a black box, called an oracle, which is able to decide certain decision problems in a single operation. The problem can be of any...
models requires exponential time.
In the USSR, a result equivalent to Baker, Gill, and Solovay's was published in 1969 by M. Dekhtiar. Later Levin
Leonid Levin
-External links:* at Boston University....
's paper, "Universal search problems", 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 problem
Search problem
In computational complexity theory and computability theory, a search problem is a type of computational problem represented by a binary relation...
s, which require finding solutions rather than simply determining existence. He provided 6 such NP-complete search problems, or universal problems, and
additionally found that each has an algorithm which solves it in optimal time.
Definitions
A decision problemDecision problem
In computability theory and computational complexity theory, a decision problem is a question in some formal system with a yes-or-no answer, depending on the values of some input parameters. For example, the problem "given two numbers x and y, does x evenly divide y?" is a decision problem...
is in NP
NP (complexity)
In computational complexity theory, NP is one of the most fundamental complexity classes.The abbreviation NP refers to "nondeterministic polynomial time."...
if it can be solved by a non-deterministic algorithm in polynomial time.
An instance of the Boolean satisfiability problem is a Boolean expression
Boolean expression
In computer science, a Boolean expression is an expression in a programming language that produces a Boolean value when evaluated, i.e. one of true or false...
that combines Boolean variables using Boolean operator
Logical connective
In logic, a logical connective is a symbol or word used to connect two or more sentences in a grammatically valid way, such that the compound sentence produced has a truth value dependent on the respective truth values of the original sentences.Each logical connective can be expressed as a...
s.
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 which says that the 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 and Johnson.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 totally equivalent, and the proof can be found in many textbooks, for example Sipser's Introduction to the Theory of Computation, section 7.3.).
Now suppose that a given problem in NP can be solved by the nondeterministic Turing machine M = (Q, Σ, s, F, δ), where Q is the set of states, Σ is the alphabet of tape symbols, s ∈ Q is the initial state, F ⊆ Q is the set of accepting states, and δ: Q × Σ → Q × Σ × {−1, +1} is the set of transitions. Suppose further 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
If and only if
In logic and related fields such as mathematics and philosophy, if and only if is a biconditional logical connective between statements....
the machine M accepts I.
The Boolean expression uses the variables set out in the following table. Here, 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)2) |
| Hik | True if the M's read/write head is at tape cell i at step k of the computation. | O(p(n)2) |
| 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
Logical conjunction
In logic and mathematics, a two-place logical operator and, also known as logical conjunction, results in true if both of its operands are true, otherwise the value of false....
of the sub-expressions in the following table, for all −p(n) ≤ i ≤ p(n) and 0 ≤ k ≤ p(n):
| Expression | Conditions | Interpretation | How many? |
|---|---|---|---|
| Tij0 | Tape cell i initially contains symbol j | Initial contents of the tape. For i > n-1 and i < 0, outside of the actual input I, the initial symbol is the special default/blank symbol. | O(p(n)) |
| Qs0 | Initial state of M. | 1 | |
| H00 | Initial position of read/write head. | 1 | |
| Tijk → ¬ Tij′k | j ≠ j′ | One symbol per tape cell. | O(p(n)2) |
| Tijk ∧ Tij′(k+1) → Hik | j ≠ j′ | Tape remains unchanged unless written. | O(p(n)2) |
| 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)2) |
(Hik ∧ Qqk ∧ Tiσk) →  (q, σ, q′, σ′, d) ∈ δ(H(i+d)(k+1) ∧ Qq′(k+1) ∧ Tiσ′(k+1)) |
k<p(n) | Possible transitions at computation step k when head is at position i. | O(p(n)2) |
 f ∈ F Qfp(n) |
Must finish in an accepting state. | 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.
There are O(p(n)2) Boolean variables, each encodeable in space O(log p(n)). The number of clauses is O(p(n)2) so the size of B is O(log(p(n))p(n)2). Thus 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 classComplexity class
In computational complexity theory, a complexity class is a set of problems of related resource-based complexity. A typical complexity class has a definition of the form:...
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
Richard Karp
Richard Manning Karp is a computer scientist and computational theorist at the University of California, Berkeley, notable for research in the theory of algorithms, for which he received a Turing Award in 1985, The Benjamin Franklin Medal in Computer and Cognitive Science in 2004, and the Kyoto...
's landmark paper, "Reducibility among combinatorial problems", in which he showed that 21 diverse combinatorial and graph theoretical problems
Karp's 21 NP-complete problems
One of the most important results in computational complexity theory was Stephen Cook's 1971 demonstration of the first NP-complete problem, the boolean satisfiability problem...
, 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
Boolean satisfiability problem
In computer science, satisfiability is the problem of determining if the variables of a given Boolean formula can be assigned in such a way as to make the formula evaluate to TRUE...
for expressions in conjunctive normal form
Conjunctive normal form
In Boolean logic, a formula is in conjunctive normal form if it is a conjunction of clauses, where a clause is a disjunction of literals.As a normal form, it is useful in automated theorem proving...
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. (First you modify the proof of the Cook-Levin theorem, so that the resulting formula is in conjunctive normal form, then you introduce new variables to split clauses with more than 3 atoms. For example, the clause (A ∨ B ∨ C ∨ D) can be replaced by the conjunction of clauses (A ∨ B ∨ Z) ∧ (¬Z ∨ C ∨ D), where Z is a new variable which will not be used anywhere else in the expression. Clauses with fewer than 3 atoms can be padded; for example, A can be replaced by (A ∨ A ∨ A), and (A ∨ B) can be replaced by (A ∨ B ∨ B) ).
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=NP problem.