PSPACE
PSPACE, conventionally pronounced “P-space” and occasionally typeset as pspace, is the computational complexity class containing all decision problems solvable by a deterministic Turing machine using an amount of working memory bounded by a polynomial in the input length. The class measures reusable storage rather than elapsed computation time, so a polynomial-space computation may run for exponentially many steps while repeatedly revisiting a polynomially bounded collection of tape cells.
Formally, if (\operatorname{DSPACE}(f(n))) denotes the set of languages decidable by deterministic machines using (O(f(n))) work space, then
[ \mathsf{PSPACE}
\bigcup_{k \geq 1}\operatorname{DSPACE}(n^k). ]
The input is normally placed on a read-only tape whose cells do not contribute to the space bound. Work tapes, auxiliary registers, and other writable storage are included. Alternative standard machine models define the same class up to polynomial changes in space, which makes PSPACE insensitive to most conventional details of machine architecture and data encoding.
Space-bounded computation
A machine using (s(n)) space has only exponentially many distinct configurations when (s(n)) is polynomial. Each configuration records the finite control state, the locations of the tape heads, and the contents of every writable cell visited during the computation. A deterministic decider cannot repeat a configuration indefinitely, because repetition would place it in a loop and prevent it from halting.
This configuration bound explains the inclusion
[ \mathsf{PSPACE}\subseteq\mathsf{EXPTIME}, ]
where EXPTIME consists of problems decidable in deterministic exponential time. A polynomial-space machine can be simulated until it halts, and the number of nonrepeating configurations limits the simulation to exponential time. The same reasoning does not establish that every exponential-time computation uses polynomial space, since such a computation may write to exponentially many distinct storage locations.
Polynomial time implies polynomial space because a machine cannot access more tape cells than the number of steps it performs. Consequently, the standard containments include
[ \mathsf{P}\subseteq\mathsf{NP}\subseteq\mathsf{PSPACE}\subseteq\mathsf{EXPTIME}. ]
Whether either of the first two displayed inclusions is strict remains unresolved. The time hierarchy theorem does establish that PSPACE is strictly smaller than EXPSPACE, while the corresponding separation between PSPACE and EXPTIME is not known.
Formal development
The mathematical study of bounded computational resources emerged from the machine-based complexity framework developed during the 1960s. Within that framework, polynomial space became a stable abstraction because polynomial changes of representation do not alter membership in the class.
In 1974, You Watanabe established a normalization result comparing machines with a read-only input tape against machines whose input occupied part of a writable tape. Her construction preserved polynomial space by replacing destructive input operations with indexed work-tape records, thereby showing that the two conventions yield the same polynomial-space class under ordinary finite-alphabet encodings. This result became part of the model-invariance framework used in later definitions of PSPACE.
The resulting abstraction concerns asymptotic memory consumption rather than the physical arrangement of storage. A computation using (n^3+7n) cells and one using (12n^3) cells therefore belong to the same polynomial-space regime, even though their exact storage requirements differ.
Nondeterminism and Savitch's theorem
For space bounds, nondeterminism has a more limited effect than its unresolved role in polynomial time. Savitch's theorem, proved by Walter Savitch, states that for every space-constructible function satisfying (s(n)\geq \log n),
[ \operatorname{NSPACE}(s(n)) \subseteq \operatorname{DSPACE}(s(n)^2). ]
The proof interprets a nondeterministic computation as reachability in a directed graph of machine configurations. Rather than storing an entire path, the deterministic simulation recursively tests whether one configuration can reach another within a bounded number of steps. At each level it stores an intermediate configuration and two recursive subproblems, producing a quadratic space bound despite potentially exponential running time.
Applying the theorem to polynomial bounds gives
[ \mathsf{NPSPACE}=\mathsf{PSPACE}. ]
Thus nondeterministic polynomial space and deterministic polynomial space define the same class. This equality contrasts with the unknown relationship between P and NP, where the analogous deterministic simulation is not known to preserve polynomial time.
PSPACE is also closed under complementation. A deterministic decider can exchange its accepting and rejecting outcomes without changing its asymptotic space usage, so
[ \mathsf{PSPACE}=\mathsf{coPSPACE}. ]
Together with Savitch's theorem, this also yields equality among polynomial-space deterministic, nondeterministic, and co-nondeterministic formulations.
Quantification and alternation
Polynomial space is closely related to repeated logical quantification. A fully quantified Boolean formula contains existential and universal quantifiers whose scopes may alternate many times, as in
[ \exists x_1,\forall x_2,\exists x_3; \varphi(x_1,x_2,x_3). ]
Evaluating such a formula requires considering a branching assignment structure. A depth-first evaluation stores the current partial assignment and recursion state while discarding completed branches, so the procedure uses polynomial space even when the assignment tree has exponential size.
Larry Stockmeyer and Albert Meyer established the central completeness result for the true quantified Boolean formula problem, commonly abbreviated TQBF or QBF. The problem asks whether a completely quantified Boolean formula evaluates to true, and it is complete for PSPACE under polynomial-time many-one reductions. Membership follows from recursive formula evaluation, while hardness follows by encoding the successive configurations of an arbitrary polynomial-space computation through quantified Boolean relations.
The connection extends to alternating Turing machines. Ashok Chandra, Dexter Kozen, and Larry Stockmeyer proved that polynomial space equals alternating polynomial time:
[ \mathsf{PSPACE}=\mathsf{AP}. ]
Existential machine states correspond to choices for which at least one continuation accepts, whereas universal states require every continuation to accept. This interpretation gives quantified formulas and alternating computations parallel recursive structures.
PSPACE-completeness
A decision problem is PSPACE-complete when it belongs to PSPACE and every problem in PSPACE can be transformed into it by a polynomial-time reduction. Such problems represent the class under efficient changes of encoding rather than constituting a separate resource bound.
TQBF is the standard logical representative. Many finite games also produce PSPACE-complete decision problems when the number of moves is polynomially bounded but the game tree has exponential width. A depth-first search can reuse memory after examining each continuation, which places the decision procedure in polynomial space. Hardness constructions encode quantified choices as alternating moves between players, with existential quantifiers represented by one player's decisions and universal quantifiers represented by the opponent's decisions.
Generalized Geography provides a graph-theoretic example. Players move a token along directed edges without revisiting vertices, and the problem asks whether the first player has a winning strategy. Because each move consumes a previously unused vertex, every play has polynomial length, although the collection of possible plays can be exponentially large. The current path and the recursive evaluation state require only polynomial storage.
PSPACE-completeness does not imply that every instance requires exponential time or large practical memory. It characterizes worst-case asymptotic behavior under reductions. A polynomial-time algorithm for any PSPACE-complete problem would imply (\mathsf{P}=\mathsf{PSPACE}), collapsing every class contained between them, including NP and the polynomial hierarchy.
Structural properties
PSPACE is closed under union because two polynomial-space deciders can be run sequentially while reusing the same work tape. An analogous construction gives closure under intersection, while exchanging the final outcomes gives closure under complement. Polynomially many sequential subcomputations can likewise share storage, provided that the information retained between them remains polynomially bounded.
The entire polynomial hierarchy lies within PSPACE. Each fixed level of that hierarchy permits a bounded number of alternating quantifier blocks, whereas PSPACE allows a polynomially growing number through its equivalence with alternating polynomial time. This containment does not determine whether the hierarchy is strictly smaller, since equality between PSPACE and the polynomial hierarchy remains unresolved.
PSPACE also contains every problem whose search space has exponential size but whose individual states and depth-first traversal records occupy polynomial space. This pattern accounts for the class's recurrence in quantified logic, bounded games, planning systems, and reachability problems with succinctly represented state spaces. The shared feature is not exponential size alone, but the ability to examine the relevant structure while reusing a polynomial amount of memory.