Problem Solving in Automata, Languages, and Complexity

6.2 Time and Space Complexity 295

(a) x E A; or

(b) There exists a partition II: = ~1~2, where $1 and x2 are nonempty, such

that ~1 E A and ~2 E A*.

So, we can build a table T of suffixes y of X, in the increasing order of the

length of the suffix, indicating whether y E A*, and use this table to determine

whether ;I: E A*. The following is the algorithm:

(1) Let T(n + 1) := 1.

(2) For each i, starting from n down to 1, do the following:

If,forsomej,i<j<n,substr(z,i,j-i+l) ~AandT(j+l)=l,

then let T(i) :=j; otherwise, let T(i) := 0.

(3) Accept x if T(1) = 1.

We observe that the above algorithm needs to simulate M for O(n2) times.

Therefore, the total time of simulation and bookkeepping is bounded by
O(n2(p&) +n)) = O(n3 -p&Q), w h’ ic is h ’ b ounded by a polynomial function

q(n). We conclude that A* E P. 0

Similar to class P, PSPACE is a mathematical representation of the class

of languages which are solvable by machines using a feasible amout of storage

space. It is, however, not considered a faithful representation of feasibly

solvable problems, since a TM using a polynomial amount of space may use

more than a polynomial amount of time. The following example shows that

a language in PSPACE can be solved using an exponential amount of time.

Whether this upper bound on time can be reduced is a major open question

in complexity theory. In particular, it is not known whether PSPACE = P.

Example 6.15 PSPACE C - EXPPOLY.

Proof. Suppose that A E PSPACE; that is, A is accepted by a one-worktape

DTM A4 with space bound nc for some constant c > 0. Let us count how

many different configurations M can have on an input of length n. First,

since we are working on a decision problem, we can ignore the output tape of

the machine A&. Next, there are at most PC possible different tape configu-

rations in the work tape of A4, where d is the number of tape symbols. (The

input tape is read-only and so has a unique tape configuration.) For each

tape configuration, there are nc possible positions of the work tape head. In

addition, there are n + 2 possible positions of the input tape head, and there

are 4 possible states for some constant q. Thus, we have obtained an upper

bound q(n + 2)ncdnc = 0(2~=+’ ) for the number of configurations of M.

Now, we can construct a new 3-worktape DTM M’ to simulate M as fol-

lows: M’ uses the first work tape to simulate the work tape of M, and uses the

second work tape to store the history of the computation of M. That is, M’

stores all the configurations M ever had in the second work tape. Initially, all

work tapes are empty. Then, M’ simulates M one move at a time. After each