PSPACE

PSPACE is formally defined as the set of languages L for which there exists a deterministic Turing machine M and a polynomial p(n) such that M decides L while using at most p(|x|) tape cells on any input x. The class is robust under variations of the machine model, including multi-tape and random-access machines, because polynomial space bounds are preserved under reasonable simulations. A crucial result is Savitch's theorem, which states that NPSPACE = PSPACE, meaning nondeterminism does not increase the power of polynomial-space computation; this follows from a recursive simulation that squares the space usage. This equality contrasts with the unresolved P vs. NP question, highlighting the distinct nature of space complexity.

A problem is PSPACE-complete if it lies in PSPACE and every other PSPACE problem reduces to it in polynomial time. The canonical PSPACE-complete problem is the quantified Boolean formula (QBF) satisfiability problem, which asks whether a fully quantified Boolean formula is true; it generalizes SAT and is complete under polynomial-time reductions. Other notable PSPACE-complete problems include the generalized geography game, the reachability game in certain graph settings, and the equivalence problem for regular expressions with intersection. These problems often involve alternating quantifiers or game-like interactions, reflecting the ability of PSPACE to model alternation. The class also contains the problem of determining the winner in many finite two-player games, such as Go on an n×n board, provided the rules are suitably generalized.

PSPACE sits in the hierarchy P ⊆ NP ⊆ PSPACE ⊆ EXPTIME, and it is known that P ≠ EXPTIME, so at least one inclusion is strict, but the exact relationships between P, NP, and PSPACE remain open. It is unknown whether P = PSPACE or NP = PSPACE, though it is widely conjectured that all inclusions are strict. PSPACE is also related to the polynomial hierarchy (PH), which is contained in PSPACE; if PH collapses, it still does not necessarily imply PSPACE = P. Another open question is whether PSPACE is closed under complement, but since PSPACE = NPSPACE and deterministic classes are closed under complement, PSPACE is indeed closed under complement. The relationship between PSPACE and randomized space classes, such as BPL, is also an active area of research, with known inclusions BPL ⊆ PSPACE.

Beyond theoretical interest, PSPACE has practical implications in formal verification and artificial intelligence. Model checking of linear temporal logic (LTL) formulas is PSPACE-complete, which means that verifying certain system properties is computationally hard but feasible in principle with polynomial memory. The game of chess, when generalized to an n×n board, is EXPTIME-complete, but many simpler games like checkers are PSPACE-complete. A lesser-known fact is that the problem of determining whether a regular expression with squaring (i.e., allowing repetition) describes all strings is PSPACE-complete, a result that has implications for pattern matching. Additionally, the class PSPACE is closed under the operation of concatenation and Kleene star, which is not trivial to prove. The study of PSPACE also led to the development of the concept of alternation, where alternating Turing machines characterize PSPACE in a way analogous to how nondeterministic machines characterize NP.

Turing machine

A mathematical model of computation that defines an abstract machine that manipulates symbols on a tape according to a set of rules.

Polynomial space

A bound on the amount of memory used by an algorithm that grows as a polynomial function of the input size.

Quantified Boolean formula

A Boolean formula with existential and universal quantifiers over its variables; the problem of evaluating such formulas is PSPACE-complete.

Savitch's theorem

A theorem stating that NPSPACE = PSPACE, showing that nondeterminism does not increase space complexity beyond polynomial.

EXPTIME

The complexity class of decision problems solvable in exponential time.