6.3 Hierarchy Theorems 303
t2 b-4 = 22n, then tz(n) = (tl(n))2 and so limn+&$)log(tl(n))/t2(n) = 0.
It follows that
P C - DTIME(2”) ; DTIME(22n) C - EXP. 0
We have shown in the last section that P C - PSPACE, but it is not known
whether the two classes are equal. It is interesting to note that we do know
that PSPACE # EXP, but we do not know whether there exists a language
in EXP \ PSPACE or in PSPACE \ EXP.
Example 6.21 EXP # PSPACE.
Proof. Since, for any constant c > 0, 2Cn < 2n2/2 for sufficiently large 72,
we have DTIME(2”“) C DTIME(2n^22 / ). By - the time hierarchy theorem, we
have EXP C DTIME(F2i2) $ DTIME(2”‘).
Now, su;pose, to the contrary, that PSPACE = EXP. We will show that
DTIME(2n2) C PSPACE, and get a contradiction.
Let L be ai arbitrary language in DTIME (2n’). Define L’ = {x$~ 1 x E
L, Ixl+t = lx12}, where $ is a symbol not used in L. Clearly, L’ E DTIME (2n),
and so, by our assumption, L’ E PSPACE. This means that there exists an
integer k such that L’ E DSPACE (d). Let A4 be a DTM accepting L’ in
space bound n Ic. Now, we construct a new DTM A4’ as follows.
On input z of length n, 1M’ copies x to a work tape and then adds
n2 - n $‘s. iV’ then simulates A4 on x$~~-~.
It is easy to see that the first step can be done using only n2 cells. Then, the
simulation uses n2k cells. So, A4’ has space bound n2’ and L(M’) = L(M) =
L. Thus, L E PSPACE. Since L is an arbitrary language in DTIME(2n2),
this shows that DTIME(2n2) C - PSPACE, and gives us a contradiction. •I
Exercise 6.3