PROOF: The first part of the proof is showing that SAT is in MP. This part is easy:

1. Use the nondeterministic ability of an NTM to guess a truth assignment T for the given expression E. If tlie encoded E is of lengtii zi, tiien 0(n) time suffices on a multitape NTM. Note that this NTM has mauy choices of move, and may have as many as 2 difierent IDs reaciied at the end of the guessing process, where each branch represents the guess of a different truth assignment.

2. Evaluate E for the truth assignment T. If E{T) = 1, then accept. Note that this part is deterministic. The fact that other branches of the NTM may not lead to acceptance has no bearing on the outcome, suice if even one satisfying truth assignment is found, the NTM accepts.

The evaluation can be done easily in O(n) time on a multitape NTM. Thus, tho entire recognition of SAT by the multitape NTM takes 0{n) time. Converting to a single-tape NTM may square the amount of time, so 0{n) time suffices on a single-tape NTM.

Now, we nmst prove the hard part: that if L is any language in ЯР, then there is a polynomial-time reduction of L to SAT. We may assume that there is some single-tape NTM M and a polynomial p{n) such that M takes no more than p{n) steps on an input of length n, along any brancli. Further, the restrictions of Theorem 8.12, which we proved for DTMs, can be proved in the same way for NTMs. Thus, we may assume that M never writes a blank, and never moves its head left of its initial head position.

Thus, if M accepts an input w, and - n, then there is a sequence of moves of M such that:

1. ao is the initial ID of M with input w.

2. ao H tti h h a*;, where fc < p(n).

3. Qjfc is an ID with an accepting state.

4. Each Qi consists of nonblanks only (except if o; ends in a state and a blank), and extends from the initial head position - the leftmost input symbol - to the right.

Our strategy can be summarized as follows.

a) Each ai can be written as a sequence of symbols ХюХц X.ip,l). One of these symbols is a state, and the others are tape symbols. As alлvays, we assume that the states and tape symbols are disjoint, so we can tell which Xij is the state, and therefore tell where the tape head is. Note that there is no reason to represent symbols to the right of the first p{n) symbols on the tape [which with the state makes an ID of length p{n) +1], because they cannot influence a move of M if M is guaranteed to halt after p{n) moves or less.

b) To describe the sequence of IDs in terras of boolean variables, we create variable yijA to represent the proposition that Xij = A. Here, i and j are each integers in the range 0 to р{п), and A is either a tape symbol or a state.

c) We express the condition that the sequence of IDs represents acceptance of an input w by writing a boolean expression that is satisfiable if and only if M accepts w by a sequence of at most p(n) moves. The satisfying assignment will be the one that tells the truth about the IDs; that is, yijA will be true if and only if = A. To make sure that the polynomial-time reduction of L(M) to SAT is correct, we write this expression so that it says the computation:

i. Starts right. That is, the initial ID is qow followed by blanks.

ii. Next move is right (i.e., the move correctly follows the rules of the TM). That is, each subsequent ID follows from the previous by one of the possible legal moves of M.

iii. Finishes right. That is, there is some ID that is an accepting state.

There are a few details that must be introduced before we can make the construction of our boolean expression precise.

First, we have specified IDs to end when the infinite tail of blanks begin. However, it is more convenient when simulating a polynomial-time computation to think of all IDs as having the same length, p{n) + 1. Thus, a tail of blanks may be present in an ID.

Second, it is convenient to assume that all computations continue for exactly p{n) moves [and therefore have p{n) + 1 IDs], even if acceptance occurs earlier. We therefore allow each ID with an accepting state to be its own successor. That is, if a has an accepting state, we allow a move a \- a. Thus, we can assume that if there is an accepting computation, then evpfn) will have an accepting ID, and that is all we have to check for the condition finishes right.

Figure 10.4 suggests what a polynomial-time computation of M looks like. The rows correspond to the sequence of IDs, and the columns are the cells of the tape that can be used in the computation. Notice that the number of squares in Fig. 10.4 is (p(n) + l) Also, the number of variables that represent each square is finite, depending only on M; it is the sum of the number of states and tape symbols of M.

Let us now give an algorithm to construct from M and w a boolean expression Em,w The overall form of Em,u! is S A N A F, where 5, Л* , and F are expressions that say M starts, moves, and finishes right.

Figure 10.4: Constructing the array of cell/ID facts

Starts Right

Xoo must be the start state go of M, oi through Xon must be w (where n is the length of w), and the remaining Xqj, must be the blank, B. That is, if w = aifla an, then:

S = Уоодо yOlai Л У02а2 Л Л Уопйп Л Уо,п+1,В Л Уо,п+-2,В Л Л Уо,р(п),П

Surely, given the encoding of M and given w, we can write S in 0[p{n)) time On a second tape of a multitape TM.

Finishes Right

Since we assume that an accepting ID repeats forever, acceptance by M is the same as finding an accepting state in Qp(n) Remember that we assume M is an NTM that, if it accepts, does so within p{n) steps. Thus, F is the OR of expressions Fj, for j = 0,1,... ,p(n), where Fj says that Xpn),j is an accepting state. That is, Fj is yp(n],j,ai V Ур(п),},а V V Ур( ),у, , where ai,a2,...,ak are all the accepting states of M. Then,

F = Fo V Pl V V Pp(n)