(

computational complexity:)

The

class of all

languages which can be recognised by a (

deterministic)

Turing machine using

polynomial memory space. This class certainly includes all problems in

P (since a

machine whose

running time is polynomial can only "

touch" polynomially many memory

cells). It also includes all problems from

NP (just generate all possible "

witnesses" (

nondeterministic inputs) for the

NDTM recognising the language) and then run the machine; since the witnesses fit in polynomial space, the whole thing does, too). And (assuming the

polynomial hierarchy does not

collapse) it includes

*every* problem in

PH, and maybe even some more.

Of course, since we don't know whether P!=NP, we certainly know even less about how large PSPACE is. However, it would be *extremely* surprising if it turned out that P=PSPACE.

The pebble game is a complete problem for PSPACE.