Cooks Theorem

 

The Turing Machine

 

A Turing Machine TM is described by the septuple

 

TM = {Q, , b, d, q0, qY, qN} where

Q = a finite set of states including a start state q0 and accepting/rejecting

states qY, and qN

= a set of symbols that are part of the language to be decided

b = the blank symbol

d = a set of transitions { (qi, sk) (qj, sh, inc)} where

qi is the initial state, qj the new state

sk the symbol under the tape head before the transition

sh the symbol in that square after the transition, and

inc = {, } the direction the tape head moves

 

Churchs Thesis any problem solvable in polynomial time on a physically realizable computer can be solved in polynomial time on a Turing Machine.

 

The Satisfiability Problem (SAT)

Given a set of n Boolean variables, {x1, x2, , xn} and a set of m CNF clauses composed of literals of these variables, is there an assignment of truth values (T and F) to these variables such that every clause is satisfied?

 

A literal is either one of the variables xi or its negation `xi

A clause in CNF form is a string of literals separated by disjunction (or) with all of

the clauses separated by conjunction (and). In our notation, we will leave out the or

operators when writing a clause.

 

Consider the set of variables {x1, x2, x3, x4} and the clauses

F = (x1 x3`x4) (`x1`x2 x4) (x1`x2`x3 x4) (x2 x3)

 

Is there an assignment of values T and F for the variables xi such that F is satisfied?

 

Although efficient algorithms exist for deciding many instances of SAT, the only

known algorithm for deciding all instances of this problem is an exhaustive search of

all 2n possible assignments for the xi. In the above example, we can readily see that

F is satisfied when {x1 = T, x2 = F, x3 = F, x4 = T}. (A clause is satisfied when any

one of the literals in the disjunction is True.)

 

While the problem of deciding an instance I of SAT is hard (no known polynomial-

time solution), given the statement of the problem instance, I, and a certificate, C(I),

the certificate can be readily verified in polynomial-time.

 

Thus SAT is in the class NP.

 

SAT is in the class NP-Complete (NPC)

To show that SAT is in NPC, we must show that

1.      SAT is in NP (discussed above)

2.      For every L NP, L ≤P SAT. Every language in NP is polynomially reducible to SAT.

 

Since every L NP can be verified in P(n) time polynomial in n, the size of the

problem instance on a Turing Machine. All of NP is reducible to a language that describes the verification process on the Turing Machine.

 

Let Q be some problem in NP, and let I be an instance of this problem. Let TMQ be a Turing machine that accepts encoded instance of Q in polynomial time if accompanied by a suitable certificate. Let P(n) be a polynomial in n with the property that TMQ recognizes every pair (x, C(x)) in the language Q, where x is a string in the language and C(x) is its certificate, in time ≤ P(n) where n is the length of x (number of symbols in the string x).

 

We need to reduce every string I in the language Q to an instance f(I) OF SAT.

 

The strategy is this the instance of SAT will be a set of clauses that together express the fact that there exists a certificate that causes TMQ to do an accepting calculation. An instance I of Q is verified if and only if the set of clauses in SAT are all true.

 

First we need to decide which Boolean variables will be used.

Let Qi,k = the state of the machine is in qk after the ith step of the checking calculation.

Si,j,h = after step i, the symbol in square j is h.

Ti,j = after step I, the tape head is positioned over square j

 

How many variables have we just introduced? Since TMQ does its calculation in time P(n), the tape head will never venture more than |P(n)| from its starting position. Thus the index j that runs through the number of tape squares takes at most O(P(n)) different values.

 

The index i runs over the steps of the accepting calculation, and takes at most O(P(n)) different values.

 

The index k indexes the (finite) number of states of TMQ and is some fixed number K. The symbols h, will be either 0, 1, or blank.

 

Hence there are all together O(P(n)2) variables a polynomial number of them.

We must now list the conditions under which a set of values assigned to these variables represent an accepting condition.

 

At each step TMQ is in at least one state

{Qi,0, Qi,1, , Qi,K}

 

since i is O(P(n)) there are O(P(n)) such clauses

 

At each step i, TMQ is in not more than one state

for each step i, and each pair j, j of states {`Qi,j,`Qi,j}

 

another O(P(n)) clauses to add to the list

Note that Qi,j `Qi,j is equivalent to the clause shown above.

 

At each step i, each tape square contains exactly one symbol from

This leads to 2 lists of clauses there is at least one symbol in each square

{Si,j,0, Si,j,1, Si,j,b}

and there is not more than one symbol in each square after step i

Si,j,k `Si,j,k which is equivalently {`Si,j,k ,`Si,j,k}

with O(P(n)2) such clauses

 

At each step the tape head is positioned over a single square

(You add the clauses now)

 

At step P(n) the machine is in state qY

 

(your turn again)

 

At each step the machine moves to its next (state, symbol, head position) in accordance with the application of the program to its previous (state, symbol)

 

{Ti,j,`Si,j,k, Si+1,j,k}

 

The tape head must be positioned over square j for the symbol written there to change

 

{`Ti,j,`Qi,k,`Si,j,t, Ti+1,j+inc}

{`Ti,j,`Qi,k,`Si,j,t, Qi+1,k}

{`Ti,j,`Qi,k,`Si,j,t, Si+1,j,t}

 

In the last 3 sets of clauses we read : either the tape head is not positioned at square j, or the present state is not qk, or the symbol just read is not t, but if they are then

 

Then there is a clause for each step of the operation i, for each square j,

-P(n) ≤ j ≤ P(n) of the tape, for each symbol t of the alphabet, and for each possible state qk of TMQ a polynomial number of clauses in all.

 

Now if we execute a recognizing computation on TMQ of a string x and its certificate, C(x), in time at most P(n), then this computation determines an assignment of values T and F to the variables listed above such that all of the clauses are simultaneously satisfied.

 

Conversely, if we have a set of values of the SAT variables in which all of the clauses are simultaneously satisfied, then that set of values describes a certificate that would cause TMQ to do a recognizing calculation on string x of Q.

 

We now have our first member of the class NP-Complete!!!!