PSPACE
PSPACE is the class of problems solvable using a polynomial amount of memory, regardless of how much time they take.
Space, not time
PSPACE contains every decision problem solvable by an algorithm that uses at most polynomial working memory in the input size. Time is unrestricted, so a PSPACE algorithm may run for exponentially many steps as long as it never uses more than polynomial space, reusing memory across the computation.
Where it sits
PSPACE contains both P and NP, and also co-NP. You can solve any NP problem in polynomial space by trying each candidate certificate in turn, reusing the same memory for each attempt. Whether PSPACE is strictly larger than NP is open.
Savitch's theorem
A surprising result, Savitch's theorem, shows that nondeterministic polynomial space equals deterministic polynomial space (NPSPACE = PSPACE). Nondeterminism, which seems so powerful for time, buys nothing extra for space at the polynomial level. This is a sharp contrast with the P vs NP situation.
PSPACE-complete problems
- Quantified Boolean formulas (SAT with alternating for-all and exists quantifiers)
- Many two-player games with polynomially bounded play
- Some planning and puzzle problems like generalized Sokoban
Games as the signature
PSPACE-complete problems often look like games: a formula with alternating quantifiers is like players taking turns, one trying to make a formula true, the other to make it false. This alternation captures adversarial reasoning, which is why bounded-length games land in PSPACE while unbounded ones climb to EXPTIME.
The chain of inclusions
The known picture is P inside NP inside PSPACE inside EXPTIME. We know P is strictly inside EXPTIME, so at least one of those inclusions is strict, but complexity theory cannot yet say which. PSPACE is a key waypoint in that unresolved map.