(
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.