Cook–Levin theorem

Cook–Levin theorem   (Redirected from Cook's theorem) Jump to navigation Jump to search 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, it is in NP, and any problem in NP can be reduced in polynomial time by a deterministic Turing machine to the Boolean satisfiability problem.

The theorem is named after Stephen Cook and Leonid Levin.

An important consequence of this theorem is that if there exists a deterministic polynomial-time algorithm for solving Boolean satisfiability, then every NP problem can be solved by a deterministic polynomial-time algorithm. The question of whether such an algorithm for Boolean satisfiability exists is thus equivalent to the P versus NP problem, which is widely considered the most important unsolved problem in theoretical computer science.

Contents 1 Contributions 2 Definitions 3 Idea 4 Proof 5 Complexity 6 Consequences 7 References Contributions The concept of NP-completeness was developed in the late 1960s and early 1970s in parallel by researchers in North America and the USSR. In 1971, Stephen Cook published his paper "The complexity of theorem proving procedures"[1] in conference proceedings of the newly founded ACM Symposium on Theory of Computing. Richard Karp's subsequent paper, "Reducibility among combinatorial problems",[2] generated renewed interest in Cook's paper by providing a list of 21 NP-complete problems. Cook and Karp each 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, in 1975, that solving NP-problems in Oracle machine models requires exponential time. That is, there exists an oracle A such that, for all subexponential deterministic-time complexity classes T, the relativized complexity class NPA is not a subset of TA. In particular, for this oracle, PA ≠ NPA.[3] In the USSR, a result equivalent to Baker, Gill, and Solovay's was published in 1969 by M. Dekhtiar.[4] Later Leonid Levin's paper, "Universal search problems",[5] 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 problems, which require finding solutions rather than simply determining existence. He provided six such NP-complete search problems, or universal problems. Additionally he found for each of these problems an algorithm that solves it in optimal time (in particular, these algorithms run in polynomial time if and only if P = NP).

Definitions A decision problem 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 operators.

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 that computes whether when that specific 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 Schematized accepting computation by the machine M.

This proof is based on the one given by Garey and Johnson.[6] 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 equivalent, and the proof can be found in many textbooks, for example Sipser's Introduction to the Theory of Computation, section 7.3., as well as in the Wikipedia article on NP).

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 F) × Σ) × (Q × Σ × {−1, +1}) is the transition relation. 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 that 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).

Variables Intended interpretation How many? Ti,j,k True if tape cell i contains symbol j at step k of the computation. O(p(n)2) Hi,k True if the M's read/write head is at tape cell i at step k of the computation. O(p(n)2) Qq,k 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 sub-expressions in the following table, for all −p(n) ≤ i ≤ p(n) and 0 ≤ k ≤ p(n): Expression Conditions Interpretation How many?

{displaystyle T_{i,j,0}} Tape cell i initially contains symbol j Initial contents of the tape. For i > n-1 and i < 0, outside of the actual input {displaystyle I} , the initial symbol is the special default/blank symbol. O(p(n)) {displaystyle Q_{s,0}} Initial state of M. 1 {displaystyle H_{0,0}} Initial position of read/write head. 1 {displaystyle neg T_{i,j,k}lor neg T_{i,j',k}} j ≠ j′ At most one symbol per tape cell. O(p(n)2) {displaystyle bigvee _{jin Sigma }T_{i,j,k}} At least one symbol per tape cell. O(p(n)2) {displaystyle T_{i,j,k}land T_{i,j',k+1}rightarrow H_{i,k}} j ≠ j′ Tape remains unchanged unless written. O(p(n)2) ¬Qq,k ∨ ¬Qq′,k q ≠ q′ Only one state at a time. O(p(n)) ¬Hi,k ∨ ¬Hi′,k i ≠ i′ Only one head position at a time. O(p(n)3) {displaystyle {begin{array}{l}(H_{i,k}land Q_{q,k}land T_{i,sigma ,k})to \bigvee _{((q,sigma ),(q',sigma ',d))in delta }(H_{i+d, k+1}land Q_{q', k+1}land T_{i, sigma ', k+1})end{array}}} k reduction from RAM computations to satisfiability". Theoretical Computer Science. 82 (1): 141–149. doi:10.1016/0304-3975(91)90177-4. ^ Stephen A. Cook (Jan 1988). "Short propositional formulas represent nondeterministic computations" (PDF). Information Processing Letters. 26 (5): 269–270. doi:10.1016/0020-0190(88)90152-4. ^ Peterson, Gary L., and John H. Reif. "Multiple-person alternation." 20th Annual Symposium on Foundations of Computer Science (sfcs 1979). IEEE, 1979. ^ Peterson, Gary, John Reif, and Salman Azhar. "Lower bounds for multiplayer noncooperative games of incomplete information." Computers & Mathematics with Applications 41.7-8 (2001): 957-992. Categories: Theorems in computational complexity theory

Si quieres conocer otros artículos parecidos a Cook–Levin theorem puedes visitar la categoría Theorems in computational complexity theory.

Deja una respuesta

Tu dirección de correo electrónico no será publicada.

Subir

Utilizamos cookies propias y de terceros para mejorar la experiencia de usuario Más información