Space Complexity & Hierarchy Theorems

PSPACE

PSPACE is the class of problems you can solve with a polynomial amount of scratch memory, however long the computation takes. Think of a chess engine analyzing a position: it may explore a staggering number of move sequences, far more than it has memory to list, but it can reuse the same board over and over, undoing each move after exploring it. With only a polynomial-size board and a polynomial-deep stack of moves to remember, it can in principle decide who wins. That bounded-memory-but-unbounded-time regime is PSPACE.

Formally, PSPACE is the union over all constants k of SPACE(n^k): the languages decided by a deterministic Turing machine using at most a polynomial number of work cells. By Savitch's theorem, allowing nondeterminism does not enlarge it, so PSPACE equals NPSPACE and we simply say PSPACE. Where does it sit? Every problem in P is in PSPACE (a polynomial-time machine touches at most polynomially many cells), and so is every problem in NP, giving P contained in NP contained in PSPACE. The key intuition for why PSPACE is large is reuse: a PSPACE machine may run for exponential time, cycling through up to 2^(poly) configurations, while never needing more than polynomial memory.

PSPACE is the natural home of two-player games and of reasoning with alternating quantifiers (the TQBF problem). Its hardest problems, the PSPACE-complete ones, capture questions like 'does the first player have a winning strategy?', which need you to consider 'there exists a move such that for all replies there exists a move ...', a back-and-forth that fills polynomial space. Honest caveats: although P is contained in PSPACE, whether the inclusion is strict (i.e. P not equal to PSPACE) is OPEN, as is NP versus PSPACE. We do know PSPACE is strictly inside EXPSPACE by the space hierarchy theorem, and is contained in EXPTIME, but pinning down its exact place among P, NP, and EXPTIME remains beyond us.

Deciding whether a fully-bracketed boolean formula with quantifiers, like 'for all x, exists y, (x or y) and (not x or not y)', is true is in PSPACE: recursively try both values of the outermost variable, reusing the same work area for each branch and undoing it before trying the next. The recursion depth is the number of variables (polynomial), so polynomial space suffices even though it explores exponentially many assignments.

PSPACE = polynomial memory, possibly exponential time; reusing the same cells is what makes it so powerful.

P is contained in NP is contained in PSPACE, but whether any of these inclusions is strict is OPEN. We only know PSPACE is strictly inside EXPSPACE (space hierarchy) and contained in EXPTIME.

Also called
polynomial spaceNPSPACE (equal by Savitch)多項式空間