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