6.4 Nondeterministic Turing Machines 311
Proof NP C - NPSPACE = PSPACE.^0
We now apply Savitch’s theorem to get some weak space hierarchy theoremsfor NSPA CE complexity classes (see also Exercise 6 of this section).
Example 6.30 Show that NSPACE(n) $ NSPACE(n210gn).
Proof By Savitch’s theorem, NSPACE(n) - C DSPACE(n2). By the space
hierarchy theorem,
DSPA CE (n2) $ DSPACE(n210gn).
Moreover, it is obvious that DSPACE(n2 log n) C - NSPACE(n2 log n). There-
fore,
NSPACE(n) $ NSPACE(n2 logn). cl
Lemma 6.31 Let q(n), sz(n), and f(n) be fully space-constructible func-
tions with s2(n) > - n and f(n) > - n. Then,
implies
NSPACE(sl(n)) C - NSPACE(s:!(n))
NSPACJqSl (f(n))) c NSPACJqs2(f (4)).Proof. For any L E NSPACE(sl (f(n))), define
where $ is a symbol not in the alphabet of L. Then, it is obvious that L’ is
in NSPACE(sl(n)). By our assumption, L’ E NSPACE (s2 (n)). This means
that there exists an NTM A42 with space bound 52(n) accepting L’. Now,
construct a two-worktape NTM M3 as follows:
(1) On input X, MS simulates an f (n)-space marking DTM to create the
string ~$-f(l~l~-l~l on the second tape.
(2) MS then simulates M2 using the second tape as the input tape and the
third tape as the work tape of M2. MS accepts the input x if and only
if M2 accepts ~$f@l)-l~l.
It is clear that MS accepts L in space bound s2( f (n)). (Note: Since sz(n) > - n,
the space used in the second tape is bounded by s2 (f(n)) .) cl
Example 6.32 Show that NSPACE(n) s NSPACE(n1*5).
Proof. By way of contradiction, suppose that NSPACE(n5) C - NSPACE(n).
Choose f(n) = n6 and n4, and apply Lemma 6.31 to the above relation. Then,
we get