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 suﬃces 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|).