6.4 Nondeterministic Turing Machines 309
NP = U NTIME(n”).
00
NPSPACE = U NSPACE(n”).
c>o
The following results are analogous to those for DTM’s proved in Section
6.2. We omit the proofs.
Theorem 6.24 Any multi-tape NTM M can be simulated by one-tape NTM’s
Mt and MS, with the following properties:
(a) L(M) = L(Mt) = L(M$).
(b) For any x E L(M), T ime&& (x) 5 c l (TimeM( for some constant c.
(c) For any x E L(M), spaceMs (x) < - c l SpaceM(x) for some constant c.
Theorem 6.25 Suppose limn,, t(n)/n = 00. Then, for any c > 0,
NTIME(t(n)) = NTIME(c l t(n)).
Theorem 6.26 For any c > 0 , NSPACE(s(n)) = NSPACE(c. s(n)).
Note that we did not list any hierarchy theorem for nondeterministic com-
plexity classes. The reason is that the proofs of hierarchy theorems about non-
deterministic classes are quite different from those for deterministic classes.
Indeed, the diagonalization argument does not work well for nondeterministic
machines. Recall the argument in the proof of Theorem 6.16: We constructed
a DTM M such that M accepts u) if and only if Mr rejects ul. Now, suppose
that MW is an NTM. Then, in order to make sure that MW rejects w, M* has
to check all computation paths of M, on w, which would take an exponential
amount of time even if M* is an NTM. Thus, the straightforward applica-
tion of diagonalization does not work for nondeterministic machines. In the
following, we use a nice relation between deterministic and nondeterministic
space complexity classes to show some weak hierarchy theorems for NSPACE
classes.
Theorem 6.27 (S avitch’s Theorem) If s(n) > - logn, then
NSPACE(s(n)) s DSPACE((s(n))2).
Proof. Let L = L(M), where M is an NTM with space bound s(n). We note
that the whole computation tree of M on an input x of length n contains at
most 2c*s(n) different configurations for some constant c (cf. Example 6.15).
Therefore, if M accepts x, then it must have an accepting computation path
of length at most 2 ‘*‘W for some constant c (note that s(n) > - log n). We now
construct a DTM M* to simulate M to find this computation path in space
(+-a2*
We note that the straightforward simulation which checks every branch