PSPACE

A language $L$ belongs to PSPACE if there is a deterministic Turing machine $M$ and a polynomial $p(n)$ such that $M$ decides $L$, and on every input of length $n$, $M$ uses at most $p(n)$ tape cells across all of its work tapes. Formally,

where $\text{SPACE}(f(n))$ denotes the class of languages decidable by a deterministic TM using $O(f(n))$ space. Crucially, there is no restriction on running time — only on the number of distinct memory configurations the machine may touch. Since a machine with $s(n)$ space and a fixed tape alphabet and state set has at most $c^{s(n)}$ distinct configurations for some constant $c$ (accounting for tape contents, head positions, and control state), any machine that halts must halt within $c^{s(n)}$ steps or else it revisits a configuration and loops forever. This gives a fundamental link: polynomial space implies at most exponential time, so

The nondeterministic analogue, NPSPACE, is defined the same way but for nondeterministic Turing machines: $L \in \text{NPSPACE}$ if some nondeterministic TM decides $L$ using $O(n^k)$ space on every branch of its computation, for some $k$. At first this looks like it should be a genuinely larger class — after all, NP (polynomial time, nondeterministic) is widely believed to be strictly larger than P. The remarkable fact, due to Savitch's Theorem, is that this intuition is wrong for space: $\text{PSPACE} = \text{NPSPACE}$. Nondeterminism, which seems to require exponentially many parallel guesses, can be simulated deterministically using only a polynomial (specifically, quadratic) blow-up in space, because a deterministic machine can reuse the same memory to sequentially check different guesses via recursive divide-and-conquer over configurations. This robustness — the fact that PSPACE doesn't care whether you allow nondeterminism — is what makes it such a clean and important class. It sits above both P and NP in the standard hierarchy of complexity classes, and it exactly captures the resources needed to solve two-player game problems with polynomially bounded game trees of unbounded depth pattern, and problems expressible with an unbounded (but fixed, polynomial) number of alternating quantifiers.

Space-bounded machines and configurations

To reason about PSPACE algorithms, it helps to fix the configuration graph model. A configuration of a Turing machine on space bound $s(n)$ encodes: the current state, the contents of all work tapes (each of length $\le s(n)$), and the positions of all tape heads. The number of distinct configurations is bounded by

for a machine with state set $Q$, tape alphabet $\Gamma$, and a constant number $k$ of tapes/heads — this is $2^{O(s(n))}$ whenever $s(n) = \Omega(\log n)$. Deciding whether $M$ accepts $w$ becomes equivalent to a reachability question on the (exponentially large but implicitly described) configuration graph: is there a path from the start configuration to an accepting configuration? This reachability view is the key to Savitch's Theorem. Rather than exploring the graph explicitly (which would take exponential space to store), the algorithm asks a recursive question: "Can I get from configuration $c_1$ to configuration $c_2$ in at most $t$ steps?" and answers it by guessing a midpoint $c_{\text{mid}}$ and recursing on two halves, each requiring only $t/2$ steps. This halves the time budget at each level of recursion while only needing to remember the current path of midpoints — which is logarithmic in the number of recursive calls, hence polynomial in the original space bound.

Savitch's algorithm, in detail

Let $N$ be a nondeterministic TM deciding a language using space $s(n) \geq \log n$. Build the deterministic algorithm `CANREACH(c1, c2, t)` that decides whether $N$ can go from configuration $c_1$ to configuration $c_2$ in at most $t$ steps. ``` function CANREACH(c1, c2, t):

# Decide whether config c2 is reachable from config c1

# in at most t steps of the nondeterministic machine N. if t == 0: return (c1 == c2) if t == 1: return (c1 == c2) or (c2 is a valid successor of c1 in one step) for each configuration cmid in the configuration space of N:

# cmid ranges over all strings that encode a legal

# configuration using <= s(n) tape cells: this is

# at most 2^(O(s(n))) possibilities, enumerated one at a time if CANREACH(c1, cmid, ceil(t/2)) and CANREACH(cmid, c2, floor(t/2)): return true return false function SAVITCH_SIMULATE(N, w): n = length(w) s = space_bound(N, n) # e.g. s(n) = n^k for the given NPSPACE machine c_start = start_configuration(N, w) T = 2^(O(s(n))) # generous bound on N's running time

# (since N halts within this many steps or loops) for each accepting configuration c_accept of N with tape usage <= s(n): if CANREACH(c_start, c_accept, T): return ACCEPT return REJECT ``` The crucial resource analysis: at recursion depth $d$, the time budget has been halved $d$ times, from $T = 2^{O(s(n))}$ down to $1$, which happens after $d = O(\log T) = O(s(n))$ levels of recursion. At each level, the algorithm stores only the current pair of configurations being compared and the candidate midpoint being tried — each of size $O(s(n))$. Since there are $O(s(n))$ levels of recursion stack, each holding $O(s(n))$ bits, the total space used is

So a language decidable in nondeterministic space $s(n)$ is decidable deterministically in space $O(s(n)^2)$. When $s(n) = n^k$ is already polynomial, $s(n)^2 = n^{2k}$ is still polynomial — hence PSPACE = NPSPACE.

The diagram: recursive reachability

Each recursive call only needs to remember the configurations at its own level of the tree — once a subcall returns, its space is reclaimed and reused for the next branch. This is the essence of why space is "reusable" in a way time is not: you cannot reuse time once it has elapsed, but you can absolutely reuse tape cells.

Space bound. As derived above, Savitch's algorithm uses $O(s(n)^2)$ space to simulate an $s(n)$-space nondeterministic machine, giving PSPACE = NPSPACE (taking $s(n)$ polynomial keeps the square polynomial). More generally the same argument gives Savitch's Theorem in full: for any $s(n) \geq \log n$,

Correctness of `CANREACH`. The proof is a clean induction on $t$.

• Base cases ($t=0,1$) are checked directly by comparing configurations or testing the (polynomially many) legal one-step transitions, which requires no recursion.
• Inductive step: `CANREACH(c1, c2, t)` returns true if and only if there exists some configuration $c_{\text{mid}}$ reachable from $c_1$ within $\lceil t/2 \rceil$ steps, from which $c_2$ is reachable within $\lfloor t/2 \rfloor$ further steps. This is exactly the definition of "$c_2$ reachable from $c_1$ within $t$ steps" split at the midpoint of the path — any path of length $t$ has some configuration at position $\lceil t/2\rceil$, and conversely concatenating two shorter reachability witnesses gives a path of length $\le t$. The correctness of the recursive calls follows by strong induction on $t$, bottoming out at the base cases.

Since $N$ decides its language using space $s(n)$, and thus (as argued) halts within $2^{O(s(n))}$ steps on every branch if it halts at all, setting $T = 2^{O(s(n))}$ and checking `CANREACH(c_start, c_accept, T)` for every valid accepting configuration correctly decides whether some accepting branch exists — which is precisely acceptance by a nondeterministic machine.

Time cost of the simulation. Savitch's construction is space-efficient but time-inefficient: the recursion tree has $O(s(n))$ levels and branches into (up to) $2^{O(s(n))}$ choices of midpoint at each level, giving a running time on the order of $2^{O(s(n))}$ — quasi-polynomial blow-up compared to what a direct simulation might achieve if unlimited space were available. This is the fundamental time–space tradeoff: Savitch buys enormous space savings at the cost of time, which is acceptable in PSPACE since only space is bounded.

PSPACE and the other classes. The chain

holds for concrete, provable reasons:

• $\text{P} \subseteq \text{NP}$: any deterministic machine is trivially a (degenerate) nondeterministic one.
• $\text{NP} \subseteq \text{PSPACE}$: a nondeterministic polynomial-time machine uses at most polynomial space (it cannot write more cells than it has time steps), so $\text{NP} \subseteq \text{NPSPACE} = \text{PSPACE}$ by Savitch.
• $\text{PSPACE} \subseteq \text{EXPTIME}$: as noted, a machine using $s(n)$ space runs for at most $2^{O(s(n))}$ steps before it must repeat a configuration (else it loops forever, contradicting that it decides a language), so polynomial space implies at most exponential time.

By the <span class="wiki-link-missing">Time Hierarchy Theorem</span> applied at the top and bottom of this chain, it is known that $\text{P} \subsetneq \text{EXPTIME}$ (strictly), which forces at least one of the inclusions above to be strict. However, it remains a major open problem whether $\text{P} = \text{NP}$, whether $\text{NP} = \text{PSPACE}$, or whether $\text{PSPACE} = \text{EXPTIME}$ individually — only the combined chain is provably non-collapsing somewhere.

Closure properties. PSPACE is closed under complement, union, intersection, concatenation, and Kleene star. Complementation is the easy and instructive case: given a machine deciding $L$ in space $s(n)$, swap its accept and reject states to decide the complement $\bar L$ in the same space bound — there is no blow-up, unlike the open question of whether NP is closed under complement (co-NP vs NP). This asymmetry is itself a clue that space and time behave very differently as resources.

Honest tradeoffs. PSPACE algorithms can be devastatingly slow in practice — Savitch's simulation and typical PSPACE-complete algorithms (e.g., minimax game-tree search with limited memoization) may take exponential time even though they use only polynomial memory. PSPACE membership is a statement about memory-feasibility, not time-feasibility; a problem being "in PSPACE" is no guarantee of a practical algorithm.

Consider a toy nondeterministic machine $N$ over a binary work tape of length $s(n) = 3$ (so configurations are tiny, for illustration), deciding whether some path leads from configuration `000` to configuration `111` using its guessed transitions, within $t = 4$ steps. Suppose the transition possibilities (nondeterministic, from tape contents alone, ignoring head/state detail for simplicity) are:

We trace `CANREACH(000, 111, 4)`:

Notice the algorithm never needed to store the whole path `000 → 001 → 011 → 111`; at any moment it only remembers the current pair of endpoints and the trial midpoint, one triple per level of recursion — three small configurations, not an exponential fan-out of paths. Even though there were two "wrong" choices available at `000` (going to `010` instead) that would have wasted a recursive attempt before backtracking, that wasted branch is discarded and its space reused, costing extra time but never extra space. This is the tradeoff in miniature: the algorithm may try the `010` branch first, fail to find a length-4 path to `111` through it (`010`→`110`→`111` is only length 2, and reachability search would confirm or refute this within the same space budget), and then backtrack to try `001` — all using the same constant-size stack frames.

:::warning[The single most dangerous confusion is equating "polynomial space" with "polynomial time." A PSPACE algorithm (including Savitch's own simulation) can legitimately run in exponential time — PSPACE membership says nothing about practical runtime, and treating a PSPACE-complete problem as "efficiently solvable" because it's "just polynomial" is a serious conceptual error.]:::

Walter Savitch proved the theorem bearing his name while studying the relative power of deterministic and nondeterministic space-bounded computation, building on earlier work formalizing space complexity by Hartmanis, Lewis, and Stearns. His 1970 result that $\text{NSPACE}(s(n)) \subseteq \text{SPACE}(s(n)^2)$ remains one of the cleanest and most surprising simulation results in complexity theory — a stark contrast to the still-open analogous question for time.

PSPACE is the natural home for problems involving unbounded-depth game trees and quantified logical reasoning. Two-player perfect-information games with polynomially describable positions but unbounded game length — generalized versions of Geography, Hex, and Checkers on $n \times n$ boards — are typically PSPACE-complete, meaning solving them optimally is believed to require essentially exhaustive game-tree search, bounded only by the memory needed to track the current line of play. This directly informs the design of AI game engines: the reason chess and Go engines rely on heuristic evaluation and pruning (like alpha-beta search or Monte Carlo tree search) rather than exact minimax to full depth is that exact solutions to generalized game problems are PSPACE-hard, and no known algorithm solves them in polynomial time. In formal verification and model checking, PSPACE captures the complexity of checking properties expressed in temporal and quantified logics over finite-state systems; tools that verify hardware or protocol correctness against specifications in linear temporal logic confront PSPACE-complete satisfiability problems as a core subroutine. In automated planning (as used in robotics and AI planning systems), determining whether a goal is reachable under a polynomially describable but combinatorially vast action space is frequently PSPACE-complete. The theoretical study of regular expressions with squaring and certain database query languages also lands squarely in PSPACE, connecting the class to practical questions in formal language theory and query optimization. Understanding PSPACE — and the looming shadow of Savitch's Theorem behind it — is essential background for the deeper study of PSPACE-Completeness and problems like the quantified Boolean formula problem that anchor the class.

Ask the tutor: Why does Savitch's Theorem not imply a similar collapse for time-bounded classes like P and NP?