48 1. Classical Computation
5.2. The class PSPACE. This class contains predicates that can be com-
puted by a TM running in polynomial (in the input length) space. The class
PSPACE also has a game-theoretic description:
Theorem 5.2. L PSPACE if and only if there exists a polynomial game
such that
L = {x: W has a winning strategy for input x}.
By a polynomial game we mean a game where the number of moves is
bounded by a polynomial (in the length of the input), players’ moves are
strings of polynomial length, and the referee’s algorithm runs in polynomial
time.
Proof. We show that a language determined by a game belongs to
PSPACE. Let the number of turns be p (|x|). We construct a sequence of
machines M1,...,Mp(|x|). Each Mk gets a prefix x, w1,b1,... of the play
that includes k moves and determines who has the winning strategy in the
remaining game.
The machine Mp(|x|) just computes the predicate W (x, w1,... ) using
referee’s algorithm. The machine Mk tries all possibilities for the next move
and consults Mk+1 to determine the final result of the game for each of
them. Then Mk gives an answer according to the following rule, which says
whether W wins. If it is W’s turn, then it suffices to find a single move for
which Mk+1 declares W to be the winner. If it is B’s turn, then W needs to
win after all possible moves of B.
The machine M0 says who is the winner before the game starts and
therefore decides L(x). Each machine in the sequence M1,...,Mp(|x|) uses
only a small (polynomially bounded) amount of memory, so that the com-
posite machine runs in polynomial space. (Note that the computation time
is exponential since each of the Mk calls Mk+1 many times.)
Let M be a machine that decides the predicate L and runs in poly-
nomial space s. We may assume that computation time is bounded by
2O(s).
Indeed, there are
2O(s)
different configurations, and after visiting the same
configuration twice the computation repeats itself, i.e., the computation be-
comes cyclic.
[To see why there are at most
2O(s)
configurations note that configuration
is determined by head position (in {0, 1,...,s}), internal state (there are |Q|
of them) and the contents of the s cells of the tape
(|A|s
possibilities where
A is the alphabet of TM); therefore the total number of configurations is
|A|s
· |Q| · s =
2O(s).]
Therefore we may assume without loss of generality that the running
time of M on input x is bounded by
2q,
where q = poly(|x|).
Previous Page Next Page