5. The hierarchy of complexity classes 49
In the description of the game given below we assume that TM keeps its
configuration unchanged after the computation terminates.
During the game, W claims that M’s result for an input string x is “yes”,
and B wants to disprove this. The rules of the game allow W to win if M(x)
is indeed “yes” and allow B to win if M(x) is not “yes”.
In his first move W declares the configuration of M after
2q−1
steps
dividing the computation into two parts. B can choose any of the parts:
either the time interval [0,
2q−1]
or the interval
[2q−1, 2q].
(B tries to catch
W by choosing the interval where W is cheating.) Then W declares the
configuration of M at the middle of the interval chosen by B and divides
this interval into two halves, B selects one of the halves, W declares the
configuration of M at the middle, etc.
The game ends when the length of the interval becomes equal to 1. Then
the referee checks whether the configurations corresponding to the ends of
this interval match (the second is obtained from the first according to M’s
rules). If they match, then W wins; otherwise B wins.
If M’s output on x is really “yes”, then W wins if he is honest and
declares the actual configuration of M. If M’s output is “no”, then W is
forced to cheat: his claim is incorrect for (at least) one of the halves. If B
selects this half at each move, than B can finally catch W “on the spot” and
win.
[2!] Problem 5.1. Prove that any predicate L(x) that is recognized by a
nondeterministic machine in space s = poly(|x|) belongs to PSPACE. (A
predicate L is recognized by an NTM M in space s(|x|) if for any x L
there exists a computational path of M that gives the answer “yes” using
at most s(|x|) cells and, for each x / L, no computational path of M ends
with “yes”.)
Theorem 5.2 shows that all the classes Σk, Πk are subsets of PSPACE.
Relations between these classes are represented by the inclusion diagram in
Figure 5.1. The smallest class is P (games of length 0); P is contained in
both classes NP and co-NP(which correspond to games of length 1); classes
NP and co-NP are contained in Σ2 and Π2 (games with two moves) and so
on. We get the class PSPACE, allowing the number of moves in a game be
polynomial in |x|.
We do not know whether the inclusions in the diagram are strict. Com-
puter scientists have been working hard for several decades trying to prove
at least something about these classes, but the problem remains open. It is
possible that P = PSPACE (though this seems very unlikely). It is also pos-
sible that PSPACE = EXPTIME, where EXPTIME is the class of languages
decidable in time
2poly(n).
Note, however, that P = EXPTIME one can
http://dx.doi.org/10.1090/gsm/047/07
Previous Page Next Page