312 COMPUTATIONAL COMPLEXITY
NPSPACE
= PSPACE I
I wif
EXP __r--,
EXPPOLYFigure 6.8: Inclusion relations between complexity classes
By Savitch’s theorem and the space hierarchy theorem,
NSPACE(n4) C - DSPACE(n’) s DSPACE(n’) C - NSPACE(n”).
This is a contradiction. cl
In Corollary 6.28, we have seen that PSPACE = NPSPACE. From this
result, it is natural to ask whether the analogous result of P = NP holds. If
we examine the proof of Savitch’s theorem, we can immediately see that the
divide-and-conquer algorithm does not apply to polynomial-time NTM’s. In
fact, we do not know of any subexponential-time DTM’s that can simulate
polynomial-time NTM’s. On the other hand, we also do not know of any proof
technique that can separate NP from P. Indeed, the question of whether P
is equal to NP has remained open since 1970, and is generally considered as
the most important open question in complexity theory.
We are going to study the P versus NP question in Chapter 7. Here,
let us just list the known and unknown relations between deterministic and
nondeterministic complexity classes. First, we know that P C NP, and NP C
PSPA CE = NPSPA CE. Next, let co-NP denote the class-of sets A whose
complements A are in NP. Since the notion of an NTM A4 accepting an
input IX: and the notion of M rejecting an input II: are not symmetric, the
nondeterministic time-bounded complexity classes are not known to be closed
under complementation. In particular, it is not known whether NP = co-NP.
These relations are summarized in Figure 6.8. In Figure 6.8, A f, B means
A $ B, A L B means that A C B but it is not known whether A = B,
A...? B means that it is not known whether A = B, and A.. # l B means that
A # B but no inclusion relation between A and B is known.
Exercise 6.4