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

Log in or register to write something here or to contact authors.