300 COMPUTATIONAL COMPLEX1TY
sz( Iw’I). For this w’, A4 has enough space to simulate MWj on w’ and to count
the number of moves of simulation. When it counts more than log(f(sl (lw’l))
moves, M accepts w’.
In summary, M uses three work tapes and it works as follows:
(1) On input w with IwI = n, M first simulates a space-marking DTM to
mark off 59(n) cells on each of the three work tapes. It then writes down
a counter 0 on the third work tape.
(2) M then simulates M, on w, using the first work tape as the work tape
of MW, and the second work tape for the extra scratch space. After each
move of simulation, it adds one to the counter on the third tape.
(3) During the simulation, if the machine MW or the counter of the third
work tape needs more space or if MW halts but rejects the input, then
M halts and accepts the input. If M, halts and accepts the input,
then M rejects the input.
The above analysis shows that M works within space 3 l s2(n) and satisfies
all requirements R,. The theorem now follows from the tape compressioin
theorem. Cl
For time complexity, the hierarchy theorem is a little weaker than the space
hierarchy theorem. We say a function t(n) is fully time-constructible if there
exists a DTM M such that for sufficiently large integers n and any input x
with 1x1 = n, TimeM = t(n). We call such a DTM a t (n)-clock machine.
Theorem 6.17 (Time Hierarchy Theorem) If tl(n) - > n + 1, t&) is fully
time-constructible, and
liminft’(ll) log(tl(n)) - - 0
n-m0^7t2 b-4
then
DTIME(ta(n)) \ DTIME(tl(n)) # 8.
Proof (Sketch). The proof is similar to that of the space hierarchy theorem.
Namely, we construct a new DTM M to simulate machine MW on input w for
at most tz(lwl) moves, and rejects the input if and only if M, accepts w in time
t2(lwl). To makesure that DTM M simulates MW for at most t2((ul() moves,
it simulataneously simulates MW and a tz(n)-clock machine MC and halts if
either of them halts. The parallel simulation is to be done by dovetailing: It
simulates MW for one move and then simulates MC for one move. The total
time used by M is, thus, bounded by c+(lwl) for some constant c > 0. By
the linear speed-up theorem, L(M) is still in DTIME(tz(n)).
The only thing that needs extra attention is that the DTM M has a fixed
number of tapes. However, the DTM MW to be simulated by M may have
an arbitrarily large number of tapes. So, M* needs to use a small number of
tapes to simulate a large number of tapes. This can be done as in Theorem