Problem Solving in Automata, Languages, and Complexity

320 COMPUTATIONAL COMPLEXITY

length < s(n) + [lognl + [IQ11 + 2. It is easy to see that we can define a

linear ordering 4 over configurations in CS such that the relation a! 4 /3 can

be verified by a DTM in space O(s( n)).

The construction of the NTM that accepts L(M) is divided into three steps.

First we observe that the predicate reach(a, ,8, Ic) is acceptable by an NTM

A41 in space O(s(n) + log Ic), if a and @ are from CZ. The NTM A41 operates

as follows:

Muchine Ml. Let a0 = QI. For each i = 0,... , k - 2, A41 guesses a

configuration a’i+l E CZ and verifies that atli = ai+l or CQ kM ai+l.

(If neither ai = cra+l nor aa kM ai+l holds, then Ml rejects on

this computation path.) Finally, Ml verifies that cq+1 = p or

ak-1 kM ,9, and accepts if this holds.

Apparently, this NTM Ml uses space O(s(n) + log k) and accepts (a!, p, k)

if and only if reach (a, ,8, Ic).

Next, we apply this machine Ml to construct another NTM A& which, on

any given configuration p, computes the exact number N of configurations in

CX that are reachable from /3, using space O(s(n)). (Note: M2 is an NTM

transducer .)

Let m be the maximum length of an accepting path on input X. Then,

T-L!= ‘J0(44). To computer N, Mz computes iteratively the number Nk

of configurations in CX that are reachable from ,8 in at most k moves, for

k = 0,.. ., nz + 1. When it finds, at stage k + 1, that Nk = Nk+l, it halts and

outputs N = &.

To compute &, we first note that NO = 1, since p is the only configuration

reachable from p in zero move. Next, for k > 0, &+I can be computed from

Nk by the following nondeterministic transducer:

Nondeterministic algorithm for computing Nk+l:

Initialize the counter &+I to 0.

For each configuration o E CX, do the following:

(1) Let ra! be FALSE.

(2) For each i = 1,... , Nk, do the following:

(a) Guess a configuration yi in CX.

(b) Verify that (i) yi- 1 3 yi if i > 1, and (ii) reuch(P, yi, k)

(by simulating machine Ml). (Reject this computation

path if (i) or (ii) does not hold.)

(c) Set ra to TRUE, if reuch(yi, a, 1).

(3) Add one to .&+ i if and only if lrcv = TRUE.

Note that M2 uses only space O(s(n)), b ecause at each step corresponding

to configuration CY and integer i, it only needs to keep the following information

in its work tape: i, k, Nk, the current Nk+l, lrcv, cq yi-1 and yi. Furthermore,

it can be checked that Mz computes correctly the number N of configurations