cooks theorem

Cook’s Theorem:

Cook’s Theorem states that-
                                             Any NP problem can be converted to SAT in polynomial time.

In order to prove this, we require a uniform way of representing NP problems. Remember that what makes
a problem NP is the existence of a polynomial-time algorithm—more specifically, a Turing machine—for
checking candidate certificates. What Cook did was somewhat analogous to what Turing did when he
showed that the Entscheidungsproblem was equivalent to the Halting Problem. He showed how to encode
as Propositional Calculus clauses both the relevant facts about the problem instance and the Turing machine
which does the certificate-checking, in such a way that the resulting set of clauses is satisfiable if and only
if the original problem instance is positive. Thus the problem of determining the latter is reduced to the
problem of determining the former.
Assume, then, that we are given an NP decision problem D. By the definition of NP, there is a polyno-
mial function P and a Turing machine M which, when given any instance I of D, together with a candidate
certificate c, will check in time no greater than P (n), where n is the length of I, whether or not c is a
certificate of I.
Let us assume that M has q states numbered 0, 1, 2, . . . , q − 1, and a tape alphabet a1 , a2 , . . . , as . We
shall assume that the operation of the machine is governed by the functions T , U , and D as described in
the chapter on the Entscheidungsproblem. We shall further assume that the initial tape is inscribed with the
problem instance on the squares 1, 2, 3, . . . , n, and the putative certificate on the squares −m, . . . , −2, −1.
Square zero can be assumed to contain a designated separator symbol. We shall also assume that the machine
halts scanning square 0, and that the symbol in this square at that stage will be a1 if and only if the candidate
certificate is a true certificate. Note that we must have m ≤ P (n). This is because with a problem instance
of length n the computation is completed in at most P (n) steps; during this process, the Turing machine
head cannot move more than P (n) steps to the left of its starting point.
We define some atomic propositions with their intended interpretations as follows:

1. For i = 0, 1, . . . , P (n) and j = 0, 1, . . . , q − 1, the proposition Qij says that after i computation
steps, M is in state j.
2. For i = 0, 1, . . . , P (n), j = −P (n), . . . , P (n), and k = 1, 2, . . . , s, the proposition Sijk says that
after i computation steps, square j of the tape contains the symbol ak .

3. i = 0, 1, . . . , P (n) and j = −P (n), . . . , P (n), the proposition Tij says that after i computation steps,
the machine M is scanning square j of the tape.

Next, we define some clauses to describe the computation executed by M :

1. At each computation step, M is in at least one state. For each i = 0, . . . , P (n) we have the clause

Qi0 ∨ Qi1 ∨ · · · ∨ Qi(q−1) ,

giving (P (n) + 1)q = O(P (n)) literals altogether.

2. At each computation step, M is in at most one state. For each i = 0, . . . , P (n) and for each pair j, k
of distinct states, we have the clause
¬(Qij ∧ Qik ),

giving a total of q(q − 1)(P (n) + 1) = O(P (n)) literals altogether.

3. At each step, each tape square contains at least one alphabet symbol. For each i = 0, . . . , P (n) and
−P (n) ≤ j ≤ P (n) we have the clause

Sij1 ∨ Sij2 ∨ · · · ∨ Sijs ,

giving (P (n) + 1)(2P (n) + 1)s = O(P (n)2 ) literals altogether.

4. At each step, each tape square contains at most one alphabet symbol. For each i = 0, . . . , P (n) and
−P (n) ≤ j ≤ P (n), and each distinct pair ak , al of symbols we have the clause

¬(Sijk ∧ Sijl ),

giving a total of (P (n) + 1)(2P (n) + 1)s(s − 1) = O(P (n)2 ) literals altogether

5. At each step, the tape is scanning at least one square. For each i = 0, . . . , P (n), we have the clause

Ti(−P (n)) ∨ Ti(1−P (n)) ∨ · · · ∨ Ti(P (n)−1) ∨ TiP (n) ,

giving (P (n) + 1)(2P (n) + 1) = O(P (n)2 ) literals altogether.

6. At each step, the tape is scanning at most one square. For each i = 0, . . . , P (n), and each distinct
pair j, k of tape squares from −P (n) to P (n), we have the clause

¬(Tij ∧ Tik ),

giving a total of 2P (n)(2P (n) + 1)(P (n) + 1) = O(P (n)3 ) literals.

7. Initially, the machine is in state 1 scanning square 1. This is expressed by the two clauses

Q01 , T01 ,

giving just two literals.
8. The configuration at each step after the first is determined from the configuration at the previous step
by the functions T , U , and D defining the machine M . For each i = 0, . . . , P (n), −P (n) ≤ j ≤
P (n), k = 0, . . . , q − 1, and l = 1, . . . , s, we have the clauses

Tij ∧ Qik ∧ Sijl → Q(i+1)T (k,l)

Tij ∧ Qik ∧ Sijl → S(i+1)jU (k,l)

Tij ∧ Qik ∧ Sijl → T(i+1)(j+D(k,l))

Sijk → Tij ∨ S(i+1)jk

The fourth of these clauses ensures that the contents of any tape square other than the currently

Sijk ∧ ¬Tij → S(i+1)jk ). These clauses contribute a total of (12s + 3)(P (n) + 1)(2P (n) + 1)q =
O(P (n)2 ) literals.

9. Initially, the string ai1 ai2 . . . ain defining the problem instance I is inscribed on squares 1, 2, . . . , n
of the tape. This is expressed by the n clauses

S01i1 , S02i2 , . . . , S0nin ,

a total of n literals.

10. By the P (n)th step, the machine has reached the halt state, and is then scanning square 0, which
contains the symbol a1 . This is expressed by the three clauses

QP (n)0 , SP (n)01 , TP (n)0 ,

giving another 3 literals.

Altogether the number of literals involved in these clauses is O(P (n)3 ) (in working this out, note that q and
s are constants, that is, they depend only on the machine and do not vary with the problem instance; thus
they do not contribute to the growth of the the number of literals with increasing problem size, which is
what the O notation captures for us). It is thus clear that the procedure for setting up these clauses, given the
original machine M and the instance I of problem D, can be accomplished in polynomial time.
We must now show that we have succeeded in converting D into SAT . Suppose first that I is a positive
instance of D. This means that there is a certificate c such that when M is run with inputs c, I, it will halt
scanning symbol a1 on square 0. This means that there is some sequence of symbols that can be placed
initially on squares −P (n), . . . , −1 of the tape so that all the clauses above are satisfied. Hence those
clauses constitute a positive instance of SAT .
Conversely, suppose I is a negative instance of D. In that case there is no certificate for I, which means
that whatever symbols are placed on squares −P (n), . . . , −1 of the tape, when the computation halts the
machine will not be scanning a1 on square 0. This means that the set of clauses above is not satisfiable, and
hence constitutes a negative instance of SAT .
Thus from the instance I of problem D we have constructed, in polynomial time, a set of clauses which
constitute a positive instance of SAT if and only I is a positive instance of D. In other words, we have
converted D into SAT in polynomial time. And since D was an arbitrary NP problem it follows that any NP
problem can be converted to SAT in polynomial time.