input w - n cells

- cells ever used-

p(n) cells

Figure 11.2: A TM that uses polynomial space

11.2.2 Relationship ofVS and MVS to Previously Defined Classes

To start, the relationships V С PS and MP С MPS should be obvious. The reason is that if a TM makes only a polynomial number of moves, then it uses no more than a polynomial number of cells; in particular, it cannot visit more cells than one plus the number of moves it makes. Once we prove PS - MPS, we shall see that in fact the three classes form a chain of containment: P С MP С PS.

An essential property of polynomial-space-bounded TMs is that they can make only an exponential number of moves before they must repeat an ID. We need this fact to prove other interesting facts about PS, and also to show that PS contains only recursive languages; i.e., languages with algorithms. Note that there is nothing in the definition of PS or MPS that requires the TM to halt. It is possible that the TM cycles forever, without leaving a polynomial-sized region of its tape.

Theorem 11.3: If M is a polynomial-space-bounded TM (deterministic or nondeterministic), and p{n) is its polynomial space bound, then there is a constant с such that if M accepts its input w of length тг, it does so within c- moves.

PROOF: The essential idea is that M must repeat an ID before making more than c+j>) moves. If M repeats an ID and then accepts, there must be a shorter sequence of IDs leading to acceptance. That is, if a F 0 \- 0 \- 7,

In fact, the general rule from Theorem 8.10 is not the strongest claim we can make. Because only 1 -- p{n) cells are used by any tape, the simulated tape heads in the many-tapes-to-one construction can get only \-\-p\n) apart. Thus, c+pI moves of the multitape TM can be simulated in О (p(n)eP< J) steps, which is less than the claimed 0(cf ),

where a is the initial ID, 0 is the repeated ID, and 7 is the accepting ID, then ah у8 h 7 is a shorter sequence of IDs leading to acceptance.

The argument that с must exist exploits the fact that there are a hmited number of IDs if the space used by the TM is Umited. In particular, let t be the number of tape symbols of M, and let s be the number of states of M. Then the number of different IDs of M when only p{n} tape cells are used is at most sp(n)tPf \ That is, we can choose one of the s states, place the head at any oip{n) tape positions, and fill the p{n) cells with any of t sequences of tape symbols.

Pick c = s + t. Then consider the binomial expansion of (t + s)+Pt , which

Notice that the second term is at least as large as sp{n)t\ which proves that i+p(n) \east equal to the number of possible IDs of M. We conclude the proof by observing that if M accepts w of length n, then it does so by a sequence of moves that does not repeat an ID. Therefore, M accepts by a sequence of moves that is no longer than the number of distinct IDs, which is с . □

We can use Theorem 11.3 to convert any polynomial-space-bounded TM into an equivalent one that always halts after making at most an exponential number of moves. The essential point is that, since we know the TM accepts within an exponential number of moves, we can count how many moves have been made, and we can cause the TM to halt if it has made enough moves without accepting.

Theorem 11.4: If L is a language in PS (respectively MVS), then L is accepted by a polynomial-space-bounded deterministic (respectively nondeterministic) TM that halts after making at most c( moves, for some polynomial q{n) and constant с > 1.

PROOF: Well prove the statement for deterministic TMs; the same argument apphes to NTMs. We know L is accepted by a TM Mi that has a polynomial space bound p{n). Then by Theorem 11.3, if Mi accepts w it does so in at most steps.

Design a new TM Ma that has two tapes. On the first tape, M-i simulates Ml, and on the second tape, M2 counts in base с up to c+l. If M2 reaches this count, it halts without accepting. M2 thus uses 1 -I- p{\w\) cells on the second tape. We also assumed that Mi uses no more than p{\w\) cells on its tape, so M2 uses no more than p{\w\) cells on its first tape as well.

If we convert M-2 to a one-tape TM M3, we can be sure that Мъ uses no more than l+p(n) cells of tape, on any input of length n. Although M3 may use the square of the running time of M2, that time is not more than ©(c ),

Figure 11.3: The recursive function reach tests whether one ID can become another within a stated number of moves

It is important to observe that, although reach calls itself twice, it makes those calls in sequence, and therefore, only one of the calls is active at a time. That is, if we start with a stack frame [Л, Ji,m], then at any time there is only one call [l2,J2,m./2], one call [/3, j3, m/4], another [7, J.i,m/8], and so

As M makes no more than dc moves for some constant d, we may pick q{n) - 2p{n) -l-logd. Then M3 makes at most c steps. Since M2 always lialts, M3 always halts. Since Mi accepts L, so do M2 and M3. Thus, M3 satisfies the statement of the theorem. □

11.2.3 Deterministic and Nondeterministic Polynomial Space

Since the comparison between P and J\fP seems so difficult, it is surprising that the same comparison between VS and NPS is easy: they are the same classes of languages. The proof involves simulating a nondeterministic TM that has a polynomial space bound p{n) by a deterministic TM with polynomial space bound 0{p{n)).

The heart of the proof is a deterministic, recursive test for whether a NTM N can move from ID 1 to ID J in at most m moves. A DTM D systematically tries all middle IDs К to check whether / can become К in m/2 moves, and then К can become J m m/2 moves. That is, imagine there is a recursive function reach{I, J, m) that decides if / h J by at most m moves.

Think of the tape of D as a stack, where the arguments of the recursive calls to reach are placed. That is, in one stack frame D holds [/, J, m]. A sketch of the algorithm executed by reach is shown in Fig. 11.3.

BOOLEAN FUNCTION reach(I,J,m) ID: I,J; INT: m; BEGIN

IF (m == 1) THEN /* basis */ BEGIN

test if I == J or I can become J after one move; RETURN TRUE if so, FALSE if not;

END;

ELSE /* inductive part */ BEGIN FOR each possible ID К DO

IF Creach СI,K,m/2) AND reach(K.J,m/2)) THEN RETURN TRUE; RETURN FALSE;

END;

END;