Cook-Levin Theorem

From ProofWiki
Jump to: navigation, search

Theorem

The Boolean Satisfiability Problem is NP-Complete.

Proof

The Boolean Satisfiability Problem is NP

Given a Boolean Satisfiability Problem with a set of variables $X$ and clauses $L$ and a possible solution to the problem, it is a trivial matter evaluate all the clauses in $L$ to verify the solution in polynomial time. Because a potential solution can be verified or rejected in polynomial time it is NP.

All NP-complete problems are polynomially reducible to the Boolean Satisfiability problem

The objective is, given a non-deterministic Turing Machine $M$ with $k$ internal states and an input $x$, to construct a set of variables and clauses that has a solution iff $M$ accepts the input $x$.

From the definition of NP we know that $M$ either accepts the input $x$ within $p(|x|)$ steps, or it does not accept the input at all, where $p$ is some polynomial.

Because a Turing Machine cannot use more squares of memory then the number of steps that it runs, we only need to concern ourselves with the first $p(|x|)$ squares of memory. Let $\Sigma$ denote the finite alphabet that the machine recognizes.


Let the variables for the Boolean Satisfiability Problem be given by

Variable Interpretation Number
$q_{jn}$ $M$ is in state $j$ on step $n$ $k*p(|x|)$
$T_{m\ \alpha\ n}$ The $m$'th square contains the symbol $\alpha \in \Sigma$ on step $n$ $|\Sigma|*p(x)^2$
$H_{m\ n}$ The $m$'th square is being looked at during step $n$ $p(|x|)^2$


And let the clauses for the Boolean Satisfiability Problem be given by

Clause Interpretation Number Length
$q_{00}$ The Machine is in the initial state $(q_0)$ on step 0. 1 Constant
$if \ m < |x| \ T_{m x_m 0}$ Let $x_m$ denote the $m$'th symbol of the input. This represents the initial state of the work tape. $|x|$ Constant
$H_{00}$ The Tape is in the initial position on step 0. 1 Constant
$if\ a\neq b \ q_{an} \implies \neg q_{bn}$ Only one internal state at a time $(k^2 - k)*n$ Constant
$if\ a\neq b \ T_{m\ a\ n} \implies \neg T_{m\ b\ n}$ Only one symbol per square at a time $(|\Sigma|^2-|\Sigma|)*p(|x|)^2$ Constant
$if\ a \neq b \ H_{an} \implies \neg H_{bn}$ Only one square is being looked at during any cycle. $p(|x|)^2 - p(|x|)$ Constant
$\neg H_{m\ n} \implies (T_{m \ \alpha \ n} = T_{m \ \alpha \ n+1})$ A square that was not looked at cannot change. $|\Sigma|*p(|x|)^2$ Constant
$q_{accept\ p(|x|)}$ $M$ is in the accepting state at the end of the computation. 1 Constant
$(q_{j\ n} \land T_{m\ \alpha \ n} \land H_{m \ n})\implies$

$\bigvee (q_{l \ n+1} \land T_{m\ \beta \ n+1} \land H_{m\pm 1\ n+1})$

These clauses encode the rules of $M$ into logical expressions.

See the explanation below.

$k*|\Sigma|*p(|x|)^2$ Varies (see below)

A production rule in a non-deterministic Turing machine can be written in the form

$(q_a , \alpha) \to (q_b , \beta , D_1) \lor (q_c , \gamma , D_2)$

meaning if the machine is in state $q_a$ and reading $\alpha$ on the tape either replace $\alpha$ with $\beta$ move one square in direction $D_1$ (either left or right) and change the internal state to $q_b$ or replace $\alpha$ with $\gamma$ move one square in the $D_2$ direction and go to internal state $q_c$. If $D_1$ is left and $D_2$ is right then this rule would translate to

$(q_a \land T_{m \ \alpha \ n} \land H_{m \ n}) \implies ((q_b \land T_{m \ \beta \ n+1} \land H_{m-1 \ n+1})\lor (q_c \land T_{m \ \gamma \ n+1} \land H_{m+1 \ n+1}) $

If the rule in the machine allows for more then two choices then this rule can be modified by adding more triplets to the right hand side of the implication rule. The length of this clause is determined by the number of choices that $M$ gives for a given internal state and a given input. Because this number of choices is bounded for any given machine, the total space used for this group of clauses is $O(p(|x|)^2)$


In total, the size of the the Boolean Satisfiability problem is $O(p(|x|)^2)$, with the constant depending on $M$.


The conversion from a description of $M$ to the Boolean Satisfiability problem is straightforward and can be done in polynomial time.


The problem described has a solution iff $M$ accepts $x$ as its input. All NP problems are polynomially reducible to the Boolean Satisfiability problem. Therefore the Boolean Satisfiability is NP-hard.


The Boolean Satisfiability Problem is NP-complete.

$\blacksquare$


Source of Name

This entry was named for Stephen Arthur Cook and Leonid Anatolievich Levin.