Problem Solving in Automata, Languages, and Complexity

310 COMPUTATIONAL COMPLEXITY

2c’s(n) and so we need 2 ‘*‘W bits to record the current computation path

under simulation. Instead, we use a divide-and-conquer algorithm to simulate

A&. To describe this algorithm, let us define some new notations. Let a0 be

the initial configuration of A4 on X. In order to check whether A4 accepts the

input, it suffices for hl* to check that, for some acepting configuration CX~,

A4 can move from a0 to af in 2’44 moves. Let reach(al, ~9, Ic) denote the

predicate that A4 can move from configuration CY.~ to configuration ~2 within k

moves. Then, what A4 needs to check is whether reach(ao, af, 2’‘@)) holds

for some accepting configuration c~f.

The critical observation in the divide-and-conquer algorithm for A&* is that,

for i > - 1,

reach(al, CQ, 2’) e (3a&each(ctl, ~3, 2i-1) and reuch(a3, a~, 2i-1)].

This relation suggests the following recursive algorithm to determine whether

reuch(al, CQ, 2i):

(1) If i = 0, then it returns YES if and only if ~1 l- a2 or al = CQ.

(2) If i > - 1, th en, for each configuration ~3, it recursively calls itself to

check whether reuch(al, ~3, 2i-1) and reuch(a3, CQ, 2i-1). It returns

YES if and only if both recursive calls return YES for some a3.

In order to estimate the space use of this recursive algorithm, let us see

how we can use a stack to simulate this divide-and-conquer algorithm in a

nonrecursive way:

(1) To determine whether reuch(cq, a~, 2’) we need to go through all con-

figurations CQ, and so we need O(s(n>) cells to store the current ~3.

(2) To determine whether reuch(cq, CQ, 2i-1) and reuch(a3, a2, 2i-1), we

need to push into the stack the information of the current setting. That

is, we need to store the current CQ, CQ, CQ and i in the stack, so that after

we find out whether reuch(cq, Q, 2’-l) and reach(a3, ~2, 2i-1), we can

continue the checking with respect to the next CY.~. The space required

to store the information is also O(s(n)).

(3) Since we start with i = c-s(n), the depth of the stack is at most c-s(n).

Thus, the total space we need is O((s(n))2).

From the above analysis, we know that a DTM &?* can determine whether

reuch(ao,cuf,2C’S(n)), for any fixed crf, within space O((s(n))2). Since the

working space for simulation on different accepting configurations at can be

re-used, the total space needed for the whole algorithm is still O((s(n))2). By

the tape compression theorem, L(M) E DS.PACE((s(n))2).^0

Corollary 6.28 PSPACE = ARSPACE.

Corollary 6.29 NP C - PSPACE.