of all language
s 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 cell
s). It also includes all problems from NP
(just generate all possible "witness
es" (nondeterministic input
s) 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.