Francais | English | Espanõl

From Wikipedia, the free encyclopedia

In computational complexity theory, the Cook-Levin Theorem, proved by Stephen Cook in his 1971 paper "The Complexity of Theorem Proving Procedures" and independently by Leonid Levin in his 1972 paper "Universal Search Problems", states that the Boolean satisfiability problem is NP-complete. Stephen Cook, who was first to press, received the Turing Award for this work, while Levin did not.

Contents 1 Definitions 2 Introduction 3 Proof 4 Consequences 5 References

[edit] Definitions

A decision problem is in NP if a non-deterministic Turing machine (NTM) 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.

[edit] Introduction

We know that P is a set of all decision problems that can be solved by deterministic algorithms in polynomial time. NP is the set of all decision problems solvable by nondeterministic algorithms in polynomial time. Since deterministic algorithms are just a special case of nondeterministic ones as shown in figure 1, we can say that P is a subset of NP. However, we don't know whether P = NP or P ≠ NP. This is one of the most famous unsolved problems in computer science theory. It may be possible that for all problems in NP, there is some undiscovered polynomial time deterministic algorithm that solves them, although most computer scientists don't expect this is true.

[edit] Proof

Cook asked the following question: Is there any single problem in NP such that if we find a polynomial time algorithm for it, then that would imply that P = NP? Cook answered this question in an affirmative manner and showed that satisfiability, or SAT, is in P if and only if P = NP. To prove this, satisfiability must be shown to be in NP and to be NP-hard. To meet the latter requirement we must show that any problem in NP is equivalent to a satisfiability problem; that is, we need to show that for any nondeterministic polynomial time Turing machine N, a Boolean formula φ(N,I) exists such that φ(N,I) is satisfiable if and only if N accepts I.

Before going any further, we will introduce an idea that will help us construct the proof. We introduce the concept of a tableau and show that it can represent a nondeterministic Turing machine N processing some input w such that |w| = n to a language in NP in at most n^k steps, for some k. A tableau for NTM N on input w is a table of size n^k × n^k where each row encodes the configuration of the NTM on a branch of its computation. Each row has the form w₁, w₂, ..., w_{i - 1}, q _j, w_i, w_{i - 1}, ..., w_m indicating that the content of the NTM's tape at that branch is the sequence of symbols w₁, ..., w_m, the location of the head of the NTM is at cell w_i, and its state is q _j. The first row of the tableau encodes the starting configuration of N on input w₁, ..., w_n, and each row follows the previous row in correspondence to the NTM's transition function. Each cell of the tableau contains a single symbol from Q ∪ Σ, and if any cell contains q_accept then the tableau is an accepting tableau.

Furthermore, before the proof of the theorem, we'll show a technical lemma. We wish to prove that a tableau can be verified in logspace. To do so, we define a language A = {(N, x, T) | T is a valid tableau of an NTM N accepting input x}. We need to show that A ∈ L. This involves checking three things. The first thing to check is that the first row of the tableau contains the starting configuration of N, that is, that the first cell contains q_start followed by each symbol of the input x in order. This only requires the first row of the tableau to be scanned and compared to the input x. The second thing to check is that the tableau is an accepting tableau; this only requires scanning each cell of the tableau and confirming that q_accept appears somewhere. Finally, each row of the tableau must follow from the previous row, according to the transition relation of the NTM N. In spite of its apparent difficulty, it is actually easy: at most two cells can change from row to successive row. If every 2-by-3 cell window of the tableau corresponds to the transition relation of N, the entire tableau is valid. For example, if the tape head is in the top, center cell of the window then it must appear in the bottow row, changing its position and the symbols on the tape in accordance with the transition relation.

Now we will prove the Cook-Levin Theorem, that says that SAT is NP-complete.

In order to show that SAT is NP-complete it must be shown that SAT ∈ NP and that it is NP-hard. Showing that SAT ∈ NP is easy; an NTM can guess assignments to each of the Boolean variables in a formula φ in sequence and accept if the guessed assignment satisfies φ.

In order to show that SAT is NP-hard, we need to show that ∀ A ∈ NP, ∃ f such that x ∈ A ⇔ f(x) ∈ SAT. That is, language A is reducible to SAT using the logspace, polynomial time function f. Let M be a NTM that accepts the language A in polynomial time n^k. Our function f will involve constructing a Boolean formula that corresponds to an |x|^k × |x|^k tableau of M on input x.

We will build a Boolean formula φ(t) that verifies the tableau for x. Each and every satisfying assignment to t corresponds to a valid accepting tableau for x. The collection of Boolean variables t encode the tableau in the following way: t_i,j,s = 1 ⇔ symbol s is written on cell i,j of the tableau, where i and j each range between 1 and |x|^k and s is a symbol from σ or Q.

The formula φ is built from four parts, φ_cell(t) ∧ φ_start(t) ∧ φ_window(t) ∧ φ_accept(t).

<math>

\phi_{\operatorname{cell}}(\mathbf{t}) = \bigwedge_{1 \leq i,j \leq n^k} \left[ \left(\bigvee_{s \in \Sigma \cup Q} t_{i,j,s} \right) \wedge \left( \bigwedge_{s,r \in \Sigma \cup Q, s \neq r} (\overline{t_{i,j,s}} \vee \overline{t_{i,j,r}})\right) \right] </math>

This formula guarantees that there is exactly one symbol in each cell of the tableau.

<math>

\phi_{\operatorname{start}}(\mathbf{t}) = t_{1,1,q_{\operatorname{begin}}} \wedge t_{1,2,x_1} \wedge t_{1,3,x_2} \wedge \cdots \wedge t_{1,1+n,x_n} \wedge t_{1,2+n,\operatorname{\textvisiblespace}} \wedge \cdots \wedge t_{1,n^k,\operatorname{\textvisiblespace}} </math>

This formula guarantees that the first row of the tableau is the starting configuration of M on x.

<math>

\phi_{\operatorname{accept}}(\mathbf{t}) = \bigvee_{1 \leq i,j \leq n^k} t_{i,j,q_{\operatorname{accept}}} </math>

This formula guarantees that the tableau contains the accept state in one of its cells.

<math>

\phi_{\operatorname{window}}(\mathbf{t}) = \bigwedge_{w \in W} \Delta(w) </math>

This formula guarantees that every 2-by-3 window of the tableau is valid. The set of all such windows, W, has fewer elements than the number of cells in the tableau. Each formula δ(w) works over exactly six cells, and so involves at most 6 × (|Q| + |σ|) variables over which ANDs and ORs may enumerate every legal set of entries.

Any satisfying assignment to variables t in the formula φ yields a valid, accepting tableau for NTM M on input x by construction. Similarly, any valid, accepting tableau corresponds to an assignment to t. Finally, the Boolean formula φ(t) is constructed in time polynomial in |x|. Consequently, ∀ A ∈ NP, ∃ f such that x ∈ A ⇔ f(x) ∈ SAT, by f(x) = φ(t), so SAT is NP-hard, and also NP-complete.

[edit] 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. This remains an open question.

The Cook-Levin 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 at most 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.

[edit] References

• Michael R. Garey and David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, 1979.
• Michael Sipser, Introduction to the Theory of Computation, PWS, 1997.
• Steven Rudich and Avi Wigderson, Computational Complexity Theory, American Mathematical Society, 2004.