296 COMPUTATIONAL COMPLEXITY
simulation move, it writes down the current configuration of M on the third
work tape. It compares this new configuration with each old configuration
stored in the second work tape to see if it has occurred before. If so, then it
halts and rejects the input (since this indicates that A.4 has entered an infinite
loop). Otherwise, it copies the configuration of the third work tape to the
second work tape and resumes the simulation.
Note that each configuration is of size O(nc), and there are at most ~(a~““)
configy;ations in the second work tape. Therefore, each comparison takes
O(2
n l C) moves, and the total time used by AZ’ is at most O((2”c+1)2 l c).
We conclude that A E DTIME(2”c’2). 0
Exercise 6.2
1.
2.
3.
4.
5.
* 6.
7.
8.
Suppose that s(n) > logn. Prove that if a Turing machine halts on all
inputs and has a space bound s(n), then it must have a time bound
An) for a constant c. Use this result to show that, for any s(n), every
set in DSPACE(s(n)) is a recursive set.
Show that every finite set of strings belongs to DTIME(n).
Let A E DTIME(f(n)) and B E DTIME(g(n)). Prove that AU B and
A n B are in RTIME ( max{ f( n) , g(n)}). Conclude from these results
that the complexity classes P, PSPACE, EXP and EXPPOLY are all
closed under Boolean operations union, intersection and complementa-
tion.In the proof of Theorem 6.10, we can actually use nine moves of M’,
instead of ten moves, to simulate at least nz moves of M. This can be
done by merging the fourth and fifth moves into one move. Can you useless than nine moves in M’ to do the same job?
Estimate how many possible local configurations there are in the proof
of Theorem 6.10.Show that every context-free language is in P (i.e., for every context-free
grammar, there is a polynomial-time parsing algorithm).Show that if A and B are in PSPACE, then Al? and A* are also in
PSPACE.
Let A, B C - l(0 + l)* + 0 such that each string x: in A or B is a binary
representation of a natural number. We let n(x) be the natural number
whose binary representation is X.