Cook–Levin theorem by Mr.Mukesh Bhukar (Lecturer, CS/IT)

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 a problem of determining whether a Boolean formula is satisfiable.

An important consequence of the theorem is this: if there were a deterministic polynomial time algorithm for solving Boolean satisfiability, then there would exist a deterministic polynomial time algorithm for solving all problems in NP. Crucially, the same follows for any NP complete problem as these are also in NP.

The question of whether such an algorithm exists is called the P=NP problem and it is widely considered the most important unsolved problem in theoretical computer science.

Contributions

The concept of NP-completeness was developed in the late 1960s and early 70s in parallel by researchers in the US and the USSR. 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 problems, 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 problem is in NP iff 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 iff 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.

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. This means that SAT is in NP by an equivalence theorem 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, is the initial state, is the set of accepting states, and 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, , , , and .

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 and :

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 = Tij(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)²)
(Hik ∧ Qqk ∧ Tiσk) → (H(i+d)(k+1) ∧ Qq′(k+1) ∧ Tiσ′(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 Qf(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.

There are O(p(n)²) Boolean variables, each encodeable in space O(logp(n)). The number of clauses is O(p(n)²) so the size of B is O(log(p(n))p(n)²). Thus the transformation is certainly a polynomial-time many-one reduction, as required.