Notice that each uses a constant number of symbols, that depends on M, but not on the length n of its input w. Thus, F has length 0{n). More importantly, the time to write F, given an encoding of M and the input w is polynomial in n; actually, F can be written in 0{p{n)) time on a multitape TM.

Next Move is Right

Assuring that the moves of M are correct is by far the most complicated part. The expression N will be the AND of expressions iV, for г = 0,1,... ,p(n) - 1, and each Nt will be designed to assure that ID a,:+i is one of the IDs that M allows to follow а . To begin the explanation of how to write Ni, observe symbol Xi+ij in Fig. 10.4. We can always determine Xi+ij from:

1. The three symbols above it: Xij-] , Xij, and Xij+i, and

2, If one of these symbols is the state of a, then the particular choice of move by the NTM M.

We shall write Ni as the Л of expressions Aij V Bij, where j = 0,1,...

Expression Aij says that:

a) The state of a; is at position j (i.e., Xij is the state), and

b) There is a choice of move of M, where Xij is the state and Xi+i is the symbol scanned, such that this move transforms the sequence of symbols Xij-iXijXij+i into . Note that if Xij is an accepting state, there is the choice of making no move at all, so all subsequent IDs are the same as the one that first led to acceptance.

Expression Bij says that:

a) The state of щ is sufiiciently far away from Xij that it cannot influence Xi+ij {i.e., neither Xij-i, Xij, nor Xij+i is a state).

b) Xi+ij = Xij.

Bij is the easier to write. Let qi,q2, - ,Ят be the states of M, and let Zi,Z2,...,Zr be the tape symbols. Then:

Bij = {yi.j-i,zi \/yi,j-i,Z2 Vyi,j-i,zJ A {yi,j,z V yi,j,z2 V V yi,j,z.) A iyi,j+i,Zt V yi,j+i,z2 V V A

{{yi,j,z, Л yi+i,j,zy) V {yi,j,Zi Л yi+i,j,zj V - V {yi,jZr Л yi+i,j,z.))

The first line of Bij says that Xtj-i is one of the tape symbols; the second line says Xij is one of the tape symbols, and the third line says the same about Xij+-\. The final line says that Xij = Xi+ij by enumerating all the possible tape symbols Z and saying that either both are Zi, or both are Z2, and so on.

There are two important special cases: either j - 0 or j - p{n). In one case there are no variables yij-i,z, and in the other, no variables y j+i,2- However, we know the head never moves to the left of its initial position, and we know it will not have time to get more than p{n) cells to the right of where it started. Thus, we may eliminate certain terms from Bio and Bi,p(,i); we leave you to make the simplification.

Now, let us consider the expressions Aij. These expressions reflect all possible relationships among the 2 x 3 rectangle of symbols in the array of Fig. 10.4: Xij, Xij+x, Xi+ij-i, Xi+ij, and An assignment of symbols

to each of these six variables is valid if:

1. Xij is a state, but Xiji and Xij+i are tape symbols.

2. Exactly one of Xi+\j-i, Xi+ij, and Xi+ij+i is a state.

3. There is a move of M that explains how Xij-iXijXij-i becomes

There are thus a finite number of assignments of symbols to the six variables that are valid. Let Aij be the OR of terms, one term for each set of six variables that form a vafid assignment.

For instance, suppose that one move of M comes from the fact that S{q, A) contains (p, C, L). Let D be some tape symbol of M. Then one valid assignment is Xij-iXijXij+i DqA and Xi+ij-iXi+iXi+ij+i = pDC. Notice how this assignment reflects the change in ID that is caused by making this move of M. The term that reflects this possibifity is

yi,j-l,d Л Л yi,j+l,a Л Л yi+i,j,d л yi+ij+i,c

If, instead, S{q,A) contains ip,C,R) (i.e., the move is the same, but the head moves right), then the corresponding vafid assignment is Xij.iXijXij+i = DqA and Xi+ij-iXi+i jATj+ij+i - DCp. The term for this valid assignment is

yi,j-l,D Л PiJq л yiJ+l,A Л J/i+l Л Уг+1,з,С Л yi+l,j+i,p

Aij is the OR of all valid terms. In the special cases j = 0 and j = p{n), we must make certain modifications to reflect the nonexistence of the variables VijZ for j < 0 or i > p{n), as we did for Aij. Finally,

Ni = (Лш V Bio) A (Ail V Sii) A - Л (Л;,р( ) V В,,( ))

and then

N = NoANi A---ANpin)-i

Although Aij and Bij can be very large if M has many states and/or tape symbols, their size is actually a constant as far as the length of input w is concerned; that is, their size is independent of n, the length of w. Thus, the length of Ni is 0{р{п)], and the length of Л is 0{p(n)). More importantly, we can write Л on a tape of a multitape TM in an amount of time that is proportional to its length, and that amount of time is polynomial in n, the length of w.

Conclusion of the Proof of Cooks Theorem

Although we have described the construction of the expression

Em.w =SAN AF

as a function of both M and w, the fact Is that only the starts right part S that depends on w, and it does so in a simple way (w is on the tape of the initial ID). The other parts, N and F, depend on M and on n, the length of only.

Thus, for any NTM M that runs in some polynomial time p(n), we can devise an algorithm that takes an input w of length тг, and produces Em,w The running time of this algorithm on a multitape, deterministic TM is 0{p(n)), and that multitape TM can be converted to a single-tape TM that runs in time 0{p{n)). The output of this algorithm is a boolean expression Em,vj that is satisfiable if and only if M accepts w within p{n) moves. □

To emphasize the importance of Cooks Theorem 10.9, let us see how Theorem 10,5 applies to it. Suppose SAT had a deterministic TM that recognized its instances in polynomial time, say time q[n). Then every language accepted by an NTM M that accepted within polynomial time p{n) would be accepted in deterministic polynomial time by the DTM whose operation is suggested by Fig. 10.5. The input щ to M is converted to a boolean expression Em,w This expression is fed to the SAT tester, and whatever this tester answers about Em,w, our algorithm answers about w.

10.2.4 Exercises for Section 10.2

Exercise 10.2.1: How many satisfying truth assignments do the following boolean expressions have? Which are in SAT?

* a) t Л (г/ V -.a;) A (г V ->y).

b) (x V y) Л {-{x V г) V iz A -y)).