47.02.05 · theoretical-cs / 02-complexity-fundamentals

Space Complexity: PSPACE, Savitch's Theorem, and PSPACE-Completeness

shipped3 tiersLean: nonepending prereqs

Anchor (Master): Arora and Barak 2009 Computational Complexity: A Modern Approach (Cambridge) §4.2-4.3 (Savitch's theorem with full proof, PSPACE-completeness, TQBF completeness with the inductive encoding of computation paths, the space hierarchy theorem, and connections to the polynomial hierarchy); Sipser 2013 §8.1-8.3; Papadimitriou 1994 Computational Complexity (Addison-Wesley) §7.2-7.3

Intuition Beginner

Time and memory are the two fundamental resources a computer uses. So far the focus has been on time: how many steps does a program need? But you can also ask a different question: how much memory does it need? This shift in perspective opens a new landscape of complexity classes and reveals structure that time alone cannot see.

The class PSPACE collects every problem that can be solved using an amount of memory that grows polynomially in the input size. Because a program that runs for a polynomial number of steps can touch at most a polynomial number of memory cells, every problem in P or NP also lives in PSPACE. The reverse is not known — PSPACE could be much larger — and the containment PSPACE within EXPTIME is known to be strict by the space hierarchy theorem.

A surprise awaits when you add nondeterminism to space-bounded computation. For time, adding nondeterminism is conjectured to add enormous power (P versus NP). For space, it adds almost nothing: Savitch's theorem shows that any problem solvable by a nondeterministic machine using $f (n)$ cells of memory can also be solved by a deterministic machine using only $f (n)^{2}$ cells. The quadratic overhead is the price of determinism, and it is remarkably small.

The canonical hard problem for PSPACE is evaluating fully quantified Boolean formulas — formulas where every variable is bound by an "exists" or "for all" quantifier, and the quantifiers can alternate. This problem, called TQBF, is to PSPACE what SAT is to NP: every PSPACE problem reduces to it, so if TQBF were easy then all of PSPACE would be easy.

Visual Beginner

The relationship between the main complexity classes discussed in this unit. Every class is contained in the ones above it.

                    EXPTIME
                   /       \
              PSPACE = NPSPACE
             /       |        \
            |       PH         |
             \      |        /
              NP -- coNP    /
                \   |      /
                  P

The key inclusions. P is inside NP inside PSPACE inside EXPTIME. NPSPACE collapses to PSPACE by Savitch. The polynomial hierarchy PH sits between NP and PSPACE but is not known to equal either. The strict inclusions P within EXPTIME and PSPACE within EXPTIME follow from hierarchy theorems.

inclusion	reason
P within NP	definition (deterministic is a special case of nondeterministic)
NP within PSPACE	a poly-time nondeterministic computation uses at most poly space
PSPACE = NPSPACE	Savitch's theorem: nondeterministic space squaring
PSPACE within EXPTIME	poly-space machine has at most exponentially many configurations

Worked example Beginner

Consider a robot navigating a grid. The grid has $n$ rows and $n$ columns, with walls in some cells. The robot starts at the top-left corner and wants to reach the bottom-right corner. At each step it can move up, down, left, or right into an adjacent cell that is not a wall.

The question "can the robot reach the goal?" is a reachability problem. A naive depth-first search uses a stack that could grow as deep as the number of cells, which is $n^{2}$ . But you can also think about it differently: does there exist a path of length at most $n^{2}$ from start to goal?

Savitch's approach is recursive. To test whether there is a path of length at most $2^{t}$ from cell $a$ to cell $b$ , pick every intermediate cell $m$ and recursively ask: is there a path of length at most $2^{t - 1}$ from $a$ to $m$ , and from $m$ to $b$ ? The recursion depth is $t$ , and each level stores one intermediate cell (which takes $O (lo g n)$ bits), so the total memory is $O (t \cdot lo g n)$ .

For a grid of size $n^{2}$ , the longest possible path has length at most $n^{2} = 2^{2 l o g n}$ , so $t = 2 lo g n$ levels of recursion suffice. The total memory is $O (lo g^{2} n)$ — far less than storing the entire grid path. This is the essence of Savitch's theorem applied to a concrete problem.

Check your understanding Beginner

Formal definition Intermediate+

Let $M$ be a Turing machine with a read-only input tape and a read-write work tape. On input $x$ of length $n$ , define $space_{M} (x)$ as the maximum number of work-tape cells that $M$ visits during its computation on $x$ . For a function $f : N \to N$ , define

SPACE (f (n)) = {L : there exists a deterministic TM M deciding L with space_{M} (x) \leq f (∣ x ∣) for all x},

and

NSPACE (f (n)) = {L : there exists a nondeterministic TM M deciding L with space_{M} (x) \leq f (∣ x ∣) for all x} .

The classes $PSPACE$ and $NPSPACE$ are the polynomial-bounded unions:

PSPACE = k \geq 0 ⋃ SPACE (n^{k}), NPSPACE = k \geq 0 ⋃ NSPACE (n^{k}) .

A configuration of a space- $S$ Turing machine on an input of length $n$ is a tuple $(q, h_{i}, h_{w}, c)$ where $q$ is the machine state, $h_{i} \in {0, \dots, n - 1}$ is the input head position, $h_{w} \in {0, \dots, S - 1}$ is the work-tape head position, and $c \in Γ^{S}$ is the work-tape contents. The number of distinct configurations is at most $∣ Q ∣ \cdot n \cdot S \cdot ∣Γ ∣^{S} = 2^{O (S + l o g n)}$ . For $S \geq lo g n$ , this is $2^{O (S)}$ .

The configuration graph $G_{M, x}$ is a directed graph whose vertices are the configurations of $M$ on input $x$ , with an edge from $C_{1}$ to $C_{2}$ if $M$ can move from $C_{1}$ to $C_{2}$ in one step. Then $M$ accepts $x$ if and only if there is a path in $G_{M, x}$ from the start configuration to an accepting configuration.

A language $L$ is PSPACE-complete if $L \in PSPACE$ and every language $A \in PSPACE$ is polynomial-time reducible to $L$ : there is a polynomial-time computable function $f$ with $x \in A ⟺ f (x) \in L$ . The language $TQBF$ (True Quantified Boolean Formulas) is the set of all fully quantified Boolean formulas that evaluate to true:

TQBF = {⟨ ϕ ⟩ : ϕ = Q_{1} x_{1} \dots Q_{m} x_{m} \cdot ψ (x_{1}, \dots, x_{m}) is true},

where each $Q_{i} \in {\exists, \forall}$ and $ψ$ is a quantifier-free Boolean formula ^{[Sipser §8.3]}.

Counterexamples to common slips Intermediate+

"Savitch's theorem implies P = NP because squaring space is cheap." Savitch addresses space, not time. The deterministic simulation of Savitch's theorem may take time exponential in the space bound (the recursive $PATH$ predicate has exponential time complexity because it enumerates all midpoints), so it gives no information about P versus NP.
"PSPACE-completeness is the same as NP-completeness but with more quantifiers." The analogy is useful but the technical difference matters. A PSPACE-complete problem allows an unbounded alternation of existential and universal quantifiers, while NP-complete problems involve a single block of existential quantifiers. The reduction must be polynomial-time, which is the same requirement, but the quantifier structure is what makes TQBF harder than SAT under standard assumptions.
"NPSPACE is larger than PSPACE because nondeterminism helps." This is precisely what Savitch's theorem disproves. The quadratic space overhead of simulating nondeterminism deterministically is modest enough that $NSPACE (n^{k}) \subseteq SPACE (n^{2 k})$ , so taking the union over all $k$ gives $NPSPACE = PSPACE$ .

Key theorem with proof Intermediate+

The central result of this unit is Savitch's theorem, which collapses nondeterministic and deterministic space up to a quadratic factor. Together with PSPACE-completeness of TQBF, it establishes the structural landscape of space-bounded computation.

Theorem (Savitch). For any space-constructible $f : N \to N$ with $f (n) \geq lo g n$ ,

NSPACE (f (n)) \subseteq SPACE (f (n)^{2}) .

In particular, $PSPACE = NPSPACE$ .

Proof. Let $L \in NSPACE (f (n))$ , decided by a nondeterministic TM $M$ using $O (f (n))$ space. The configuration graph $G_{M, x}$ has at most $N = 2^{O (f (n))}$ vertices. Define a recursive predicate:

PATH (a, b, t) = {10 if there is a path from a to b of length \leq 2^{t} in G_{M, x}, otherwise.

For the base case $t = 0$ : check whether $a = b$ or there is an edge from $a$ to $b$ (at most one step). For $t \geq 1$ : there is a path of length at most $2^{t}$ from $a$ to $b$ if and only if there exists a midpoint $c$ such that both $PATH (a, c, t - 1)$ and $PATH (c, b, t - 1)$ hold.

The deterministic algorithm evaluates $PATH (C_{s}, C_{a}, T)$ where $C_{s}$ is the start configuration, $C_{a}$ is any accepting configuration, and $2^{T} \geq N$ . It iterates over all possible midpoints $c$ (each represented in $O (f (n))$ space), recursively checks both halves, and accepts if any midpoint works. The recursion depth is $T = O (f (n))$ . At each level the algorithm stores one midpoint configuration using $O (f (n))$ space, and the two recursive calls reuse the same space. Total space: $O (T \cdot f (n)) = O (f (n)^{2})$ . $□$

Corollary. $PSPACE = NPSPACE$ .

Proof. $NSPACE (n^{k}) \subseteq SPACE (n^{2 k})$ by Savitch. Taking the union over all $k$ gives $NPSPACE \subseteq PSPACE$ . The reverse inclusion $PSPACE \subseteq NPSPACE$ is immediate since deterministic machines are a special case. $□$

Theorem (TQBF is PSPACE-complete). $TQBF$ is PSPACE-complete.

Proof sketch. Membership in PSPACE: evaluate a fully quantified Boolean formula $ϕ = Q_{1} x_{1} \dots Q_{m} x_{m} \cdot ψ$ recursively. Try both values of $x_{1}$ ; if $Q_{1} = \exists$ , accept if either recursive call accepts; if $Q_{1} = \forall$ , accept if both accept. The recursion depth is $m \leq poly (n)$ and each level stores one assignment to the already-processed variables, using polynomial space total.

Hardness: given a PSPACE machine $M$ using $S = n^{c}$ space and an input $x$ , encode the computation as a quantified formula. The key idea is the same Savitch-style recursive predicate. Define $REACH (C_{1}, C_{2}, t)$ to mean "configuration $C_{2}$ is reachable from $C_{1}$ in at most $2^{t}$ steps." Then $REACH (C_{1}, C_{2}, t)$ holds if and only if there exists a midpoint $C_{m}$ such that for all intermediate configurations, both halves are reachable:

REACH (C_{1}, C_{2}, t) ⟺ \exists C_{m} \forall (C_{a}, C_{b}) \in {(C_{1}, C_{m}), (C_{m}, C_{2})} : REACH (C_{a}, C_{b}, t - 1) .

The alternation of quantifiers mirrors the recursion. Unrolling $T = O (S)$ levels gives a fully quantified formula of polynomial size. $□$

Bridge. This theorem is the foundational reason space-bounded complexity has a different character from time-bounded complexity: nondeterminism costs only a quadratic factor in space (Savitch) but is conjectured to cost an exponential factor in time (P versus NP), and this is exactly the structural asymmetry that makes PSPACE a natural home for alternating quantifiers and two-player games. The recursive PATH predicate builds toward the Immerman-Szelepcsenyi theorem 47.02.06, where the same configuration-graph reachability question is studied at the logarithmic level, and it appears again in the IP = PSPACE proof 47.03.04, where the arithmetisation of the quantifier alternations gives an interactive protocol. The central insight is that space can be reused — the two recursive calls in Savitch share the same memory — whereas time cannot, putting these together gives a deterministic simulation whose resource consumption is multiplicative in space but exponential in time, and the bridge is that TQBF packages this recursive reachability as a single formula whose alternating quantifiers are the logical fingerprint of PSPACE.

Exercises Intermediate+

Exercise 6 (hard, symbolic).

Let $GG = {⟨ G, s, t, k ⟩ : G is a directed graph and the geography game starting from s with k moves reaches t}$ be the generalised geography problem. Show that $GG$ is PSPACE-hard by reducing from TQBF.

Hint

Model existential quantifiers as "Player 1 picks a value" and universal quantifiers as "Player 2 picks a value." Construct a graph where the two players alternate moves corresponding to quantifier assignments.

Answer

Given a QBF formula $Q_{1} x_{1} \dots Q_{m} x_{m} \cdot ψ$ , construct a graph for the geography game. Create a path of diamond gadgets: for each variable $x_{i}$ , create a node where the current player chooses left ( $x_{i} = 0$ ) or right ( $x_{i} = 1$ ). If $Q_{i} = \exists$ , it is Player 1's turn; if $Q_{i} = \forall$ , it is Player 2's turn. After all variables are set, the game enters a subgraph encoding $ψ$ : Player 1 wins iff $ψ$ is satisfied by the chosen assignment. Player 1 has a winning strategy in this game iff the QBF formula is true. The reduction is polynomial-time, so GG is PSPACE-hard. Membership in PSPACE follows from the standard game-tree search using polynomial space. Rubric: full credit for the quantifier-to-player construction and the polynomial-time reduction argument.

Exercise 7 (hard, symbolic).

Prove the space hierarchy theorem for space-constructible functions: if $f (n) = o (g (n))$ and both are space-constructible with $g (n) \geq lo g n$ , then $SPACE (f (n)) ⊊ SPACE (g (n))$ .

Hint

Diagonalise: define a language that disagrees with every $f (n)$ -space machine on at least one input by simulating each machine for $g (n)$ steps and flipping the answer.

Answer

Define a TM $D$ that on input $⟨ M ⟩$ (encoding of machine $M$ ) simulates $M$ on $⟨ M ⟩$ using at most $g (n)$ space, where $n = ∣ ⟨ M ⟩ ∣$ . If $M$ uses more than $g (n)$ space, reject. If $M$ halts, output the opposite of $M$ 's answer. $D$ uses $O (g (n))$ space (the simulation overhead is a constant factor since $g$ is space-constructible and provides enough room), so $L (D) \in SPACE (O (g (n))) = SPACE (g (n))$ by the tape compression theorem.

Now suppose $L (D) \in SPACE (f (n))$ , decided by machine $M_{0}$ . For large $n$ , $M_{0}$ on input $x$ of length $n$ uses at most $f (n) < g (n)$ space. Run $D$ on input $⟨ M_{0} ⟩$ : $D$ successfully simulates $M_{0}$ (since $M_{0}$ uses less than $g (∣ ⟨ M_{0} ⟩ ∣)$ space) and outputs the opposite, contradicting $M_{0} = D$ . Hence $L (D) \in / SPACE (f (n))$ . Rubric: full credit for the diagonal machine construction, the space analysis, and the contradiction argument.

Exercise 8 (hard, symbolic).

Show that the polynomial hierarchy $PH \subseteq PSPACE$ . Conclude that if $P = PSPACE$ then $PH$ collapses to $P$ .

Hint

Each level $Σ_{k}$ of PH involves $k$ alternating quantifiers over polynomial-length certificates. Evaluate these quantifiers using polynomial space by recursion.

Answer

A language $L \in Σ_{k}$ is decided by a polynomial-time predicate with $k$ alternating quantifier blocks: $x \in L ⟺ \exists y_{1} \forall y_{2} \dots Q_{k} y_{k} : R (x, y_{1}, \dots, y_{k})$ where each $∣ y_{i} ∣ \leq poly (∣ x ∣)$ . A polynomial-space machine evaluates this by recursion on the quantifiers: for $\exists y_{1}$ , iterate over all polynomial-length strings $y_{1}$ (there are $2^{poly (n)}$ many) and accept if any recursive call accepts; for $\forall y_{2}$ , accept if all recursive calls accept. Each recursive call adds one polynomial-length string to the stack, and the stack depth is $k = O (1)$ . Total space: $O (k \cdot poly (n)) = poly (n)$ . Hence $Σ_{k} \subseteq PSPACE$ for every fixed $k$ , and $PH = ⋃_{k} Σ_{k} \subseteq PSPACE$ . If $P = PSPACE$ then $PH \subseteq P$ , so PH collapses to P. Rubric: full credit for the recursive quantifier evaluation argument and the collapse conclusion.

Advanced results Master

The theory of PSPACE extends well beyond the core theorems. The results below develop the space hierarchy, sharpen the relationship between time and space, and explore the structure of PSPACE-complete problems.

Theorem 1 (Savitch's theorem, detailed analysis). The deterministic simulation in Savitch's theorem uses time $2^{O (f (n))}$ even though space is only $f (n)^{2}$ . This exponential time overhead is inherent in the recursive approach: the $PATH (a, b, t)$ predicate explores all $2^{O (f (n))}$ midpoints at each level, and the recursion has $O (f (n))$ levels. Any improvement to polynomial time while maintaining polynomial space would resolve open questions in complexity theory, since $NL \subseteq P$ would follow from polynomial-time simulation of nondeterministic logarithmic space ^{[Arora-Barak §4.2]}.

Theorem 2 (TQBF completeness, full proof). The PSPACE-completeness of TQBF requires two directions. Membership was sketched above; the hardness direction encodes the PSPACE computation as a quantified formula using a technique analogous to the Cook-Levin construction 47.02.02. Given $M$ using $S = n^{c}$ space, let $C_{s}$ and $C_{a}$ be start and accepting configurations. Define $ϕ_{t} (C_{1}, C_{2})$ to encode " $C_{2}$ is reachable from $C_{1}$ in at most $2^{t}$ steps." For $t = 0$ , $ϕ_{0}$ checks that $C_{1} = C_{2}$ or there is a single-step transition, expressible as a constant-size Boolean formula. For $t \geq 1$ , apply the Savitch recursion:

ϕ_{t} (C_{1}, C_{2}) = \exists C_{m} \forall i \in {0, 1} : ϕ_{t - 1} (C_{1}^{(i)}, C_{2}^{(i)})

where $(C_{1}^{(0)}, C_{2}^{(0)}) = (C_{1}, C_{m})$ and $(C_{1}^{(1)}, C_{2}^{(1)}) = (C_{m}, C_{2})$ . Unrolling $T = O (S)$ levels gives a quantified formula of size polynomial in $n$ (each configuration is $O (S)$ bits and $T = O (S)$ , but the key observation is that the same variable names are reused across levels). The formula is true if and only if $M$ accepts $x$ , so the reduction is correct ^{[Sipser §8.3]}.

Theorem 3 (space hierarchy theorem). For space-constructible $f, g$ with $f (n) = o (g (n))$ and $g (n) \geq lo g n$ , the inclusion $SPACE (f (n)) ⊊ SPACE (g (n))$ is strict ^{[Arora-Barak §4.1]}. The proof diagonalises against all $f (n)$ -space machines: construct a language $L_{D}$ that on input $⟨ M ⟩$ simulates $M$ on $⟨ M ⟩$ for $g (n)$ space and flips the answer. As long as $g (n)$ exceeds the simulation overhead, $L_{D}$ separates the classes. Important corollaries: $L ⊊ PSPACE$ and $PSPACE ⊊ EXPSPACE$ .

Theorem 4 (PSPACE and games). Many two-player games of polynomial length are PSPACE-complete. The generalised geography problem and the problem of deciding whether the first player has a winning strategy in generalised chess, Go, or checkers on an $n \times n$ board are PSPACE-complete ^{[Arora-Barak §4.3]}. The correspondence between alternating quantifiers and alternating game moves is the structural reason: an existential quantifier corresponds to "there exists a move for Player 1" and a universal quantifier to "for every response by Player 2," so TQBF is equivalent to asking whether Player 1 has a winning strategy in a polynomial-depth game tree.

Theorem 5 (PSPACE and the polynomial hierarchy). The polynomial hierarchy $PH = ⋃_{k \geq 0} Σ_{k}^{P}$ satisfies $PH \subseteq PSPACE$ . Each level $Σ_{k}^{P}$ involves $k$ alternating polynomial-length quantifiers over a polynomial-time predicate, and evaluating these quantifiers sequentially using polynomial space places $Σ_{k}^{P} \subseteq PSPACE$ . Whether $PH = PSPACE$ is open; if they are equal, then the polynomial hierarchy collapses. This is dual to the P vs NP question: both ask whether additional quantifier alternation adds computational power ^{[Arora-Barak §5.2]}.

Synthesis. The foundational reason the space complexity landscape differs from the time landscape is that space can be reused: Savitch's theorem exploits this by having two recursive calls share the same memory, which builds toward the surprising equality PSPACE = NPSPACE and this is exactly the structural fact that makes space more tractable than time as a resource to analyse. The alternating quantifiers in TQBF are dual to the alternating moves in two-player games, and this is exactly the bridge to interactive proofs 47.03.04, where the IP = PSPACE theorem shows that every PSPACE computation can be verified by a polynomial-time verifier interacting with a powerful prover. The central insight unifying these results is that the configuration graph of a space-bounded machine has polynomial diameter when measured in the logarithm of the number of configurations, and putting these together the Savitch recursion, the TQBF encoding, and the game-tree characterisation all express the same polynomial-space reachability question in different languages. The space hierarchy theorem 47.02.01 provides the strict separations that make this structure non-vacuous, and the generalises connection from PSPACE to the polynomial hierarchy 47.02.03 shows that space complexity subsumes the entire quantifier-alternation hierarchy.

Full proof set Master

Proposition 1 (Savitch's theorem). For space-constructible $f (n) \geq lo g n$ , $NSPACE (f (n)) \subseteq SPACE (f (n)^{2})$ .

Proof. Let $M$ be a nondeterministic TM deciding $L$ in space $O (f (n))$ . The configuration graph $G_{M, x}$ has $N = 2^{O (f (n))}$ vertices. Define $PATH (a, b, t)$ as above. The algorithm for $PATH (a, b, t)$ : if $t = 0$ , return 1 iff $a = b$ or $(a, b)$ is an edge. If $t \geq 1$ , for each vertex $c$ (enumerated in $O (f (n))$ space): compute $PATH (a, c, t - 1)$ ; if it returns 1, compute $PATH (c, b, t - 1)$ ; if both return 1, return 1. After all midpoints, return 0.

Space analysis: the recursion depth is $t$ . At each level, the algorithm stores one midpoint $c$ using $O (f (n))$ space and one return value. The two recursive calls are sequential and reuse space. Total space: $O (t \cdot f (n))$ . Setting $t = O (f (n))$ so that $2^{t} \geq N$ gives total space $O (f (n)^{2})$ . $□$

Proposition 2 (PSPACE = NPSPACE). $PSPACE = NPSPACE$ .

Proof. For any $k$ , $NSPACE (n^{k}) \subseteq SPACE (n^{2 k})$ by Proposition 1. Union over $k$ : $NPSPACE = ⋃_{k} NSPACE (n^{k}) \subseteq ⋃_{k} SPACE (n^{2 k}) = PSPACE$ . The reverse inclusion is immediate. $□$

Proposition 3 (TQBF is in PSPACE). The language TQBF is decidable in polynomial space.

Proof. Given a QBF $ϕ = Q_{1} x_{1} \dots Q_{m} x_{m} \cdot ψ$ , evaluate recursively. The recursive procedure takes a partial assignment $σ$ to the first $i$ variables and evaluates the remaining quantifiers. For $Q_{i + 1} = \exists$ : try $σ [x_{i + 1} := 0]$ and $σ [x_{i + 1} := 1]$ ; accept if either recursive call accepts. For $Q_{i + 1} = \forall$ : accept if both recursive calls accept. When all variables are assigned, evaluate $ψ$ in polynomial time. Each recursive level stores one additional variable value, so the space is $O (m) \leq O (∣ ϕ ∣)$ . $□$

Proposition 4 (PSPACE-completeness of TQBF). Every language $L \in PSPACE$ is polynomial-time reducible to TQBF.

Proof. Let $M$ decide $L$ in space $p (n)$ for polynomial $p$ . For input $x$ , construct the formula $ϕ_{T} (C_{s}, C_{a})$ using the recursive Savitch encoding with $T = O (p (n))$ levels. At each level, a configuration is encoded by $O (p (n))$ Boolean variables. The formula $ϕ_{0} (C_{1}, C_{2})$ checks equality or single-step reachability with a constant-size circuit. The recursion $ϕ_{t} = \exists C_{m} \forall i : ϕ_{t - 1} (C_{1}^{(i)}, C_{2}^{(i)})$ introduces $O (p (n))$ new variables per level and $O (p (n))$ levels, giving a formula of total size $poly (n)$ . The formula is true iff $M$ accepts $x$ . The construction is polynomial-time since each level's encoding is polynomial and there are polynomially many levels. $□$

Proposition 5 (space hierarchy). If $f (n)$ is space-constructible and $f (n) = o (g (n))$ with $g (n) \geq lo g n$ space-constructible, then $SPACE (f (n)) ⊊ SPACE (g (n))$ .

Proof. Define TM $D$ : on input $x$ of length $n$ , use $g (n)$ space to simulate $M_{x}$ on $x$ (where $M_{x}$ is the machine encoded by $x$ , padded if needed). If $M_{x}$ attempts to use more than $g (n)$ space, reject. Otherwise, output the complement of $M_{x}$ 's output. $D$ uses $O (g (n))$ space, so $L (D) \in SPACE (O (g (n))) = SPACE (g (n))$ .

Suppose $L (D) \in SPACE (f (n))$ . Then some machine $M_{0}$ decides $L (D)$ in space $c \cdot f (n)$ for constant $c$ . For large enough $n$ , $c \cdot f (n) < g (n)$ . Let $x_{0}$ encode $M_{0}$ with appropriate padding. Then $D$ on $x_{0}$ successfully simulates $M_{0}$ (which uses $< g (∣ x_{0} ∣)$ space) and outputs the opposite, so $x_{0} \in L (D) ⟺ x_{0} \in / L (M_{0})$ , contradicting $M_{0}$ deciding $L (D)$ . $□$

Connections Master

Time complexity and P/NP 47.02.01 provides the foundational complexity classes that PSPACE extends. The containment $P \subseteq NP \subseteq PSPACE$ follows from P/NP theory, and the polynomial hierarchy 47.02.03 sits between NP and PSPACE. This unit owns the space-bounded analogue and the structural collapse PSPACE = NPSPACE.
NP-completeness 47.02.02 introduces the reduction technique that PSPACE-completeness mirrors. The Cook-Levin reduction from any NP machine to SAT is the template for the reduction from any PSPACE machine to TQBF, with the key difference being the unbounded quantifier alternation.
L, NL, and Immerman-Szelepcsenyi 47.02.06 studies space-bounded classes below PSPACE. Savitch's theorem applies at the logarithmic level too, giving $NL \subseteq SPACE (lo g^{2} n)$ , but the Immerman-Szelepcsenyi theorem gives the tighter result $NL = coNL$ , which has no known time analogue.
Interactive proofs 47.03.04 establish that $IP = PSPACE$ , giving a characterisation of PSPACE in terms of interactive protocols. The arithmetisation of the TQBF quantifier structure is the core of the LFKN-Shamir proof, and the PSPACE-completeness of TQBF developed here is the starting point for that construction.
Models of computation 42.04.01 supply the Turing machine model and configuration formalism that underlies the space-bounded analysis. The configuration graph is a refinement of the universal machine construction from that unit.

Historical & philosophical context Master

Walter Savitch proved his theorem in 1970 in his PhD thesis at the University of California, Berkeley, under the supervision of Manuel Blum. The result appeared in the Journal of Computer and System Sciences as "Relationships Between Nondeterministic and Deterministic Tape Complexities" (Savitch, 1970). At the time, the relationship between nondeterministic and deterministic space was wide open, and Savitch's quadratic bound was a strikingly strong result — it showed that nondeterminism is far less powerful in the space setting than was (and still is) conjectured for time ^{[Sipser §8.2]}.

The PSPACE-completeness of TQBF was established by Larry Stockmeyer and Albert Meyer in 1973 in their paper "Word Problems Requiring Exponential Time," which also introduced the polynomial hierarchy. The connection between PSPACE and two-player games was explored by Schaefer (1978), who proved PSPACE-completeness for a wide range of games. The geography game reduction became a standard textbook example.

The equality IP = PSPACE, proved by Lund, Fortnow, Karloff, and Nisan (1990) and Shamir (1990), gave a completely unexpected characterisation of PSPACE through interaction rather than quantifiers, connecting this unit to the interactive proof framework. The space hierarchy theorem, a consequence of earlier work by Hartmanis, Lewis, and Stearns (1965), provides the strict inclusions that give the theory nontrivial content.

Bibliography Master

@article{savitch1970relationships,
  author  = {Savitch, Walter J.},
  title   = {Relationships between nondeterministic and deterministic tape complexities},
  journal = {Journal of Computer and System Sciences},
  volume  = {4},
  number  = {2},
  year    = {1970},
  pages   = {177--192}
}

@article{stockmeyer1973word,
  author  = {Stockmeyer, Larry J. and Meyer, Albert R.},
  title   = {Word problems requiring exponential time},
  journal = {Proceedings of the 5th Annual ACM Symposium on Theory of Computing},
  year    = {1973},
  pages   = {1--9}
}

@article{shamir1990ip,
  author  = {Shamir, Adi},
  title   = {{IP} = {PSPACE}},
  journal = {Journal of the ACM},
  volume  = {39},
  number  = {4},
  year    = {1992},
  pages   = {869--877}
}

@article{lund1990algebraic,
  author  = {Lund, Carsten and Fortnow, Lance and Karloff, Howard and Nisan, Noam},
  title   = {Algebraic methods for interactive proof systems},
  journal = {Proceedings of the 31st Annual Symposium on Foundations of Computer Science},
  year    = {1990},
  pages   = {2--10}
}

@article{schaefer1978complexity,
  author  = {Schaefer, Thomas J.},
  title   = {The complexity of {S}atisfiability problems},
  journal = {Proceedings of the 10th Annual ACM Symposium on Theory of Computing},
  year    = {1978},
  pages   = {216--226}
}

@book{sipser2013introduction,
  author    = {Sipser, Michael},
  title     = {Introduction to the Theory of Computation},
  publisher = {Cengage Learning},
  edition   = {3rd},
  year      = {2013}
}

@book{arora2009computational,
  author    = {Arora, Sanjeev and Barak, Boaz},
  title     = {Computational Complexity: A Modern Approach},
  publisher = {Cambridge University Press},
  year      = {2009}
}

@book{papadimitriou1994computational,
  author    = {Papadimitriou, Christos H.},
  title     = {Computational Complexity},
  publisher = {Addison-Wesley},
  year      = {1994}
}

Prerequisites

47.02.01 pending
42.04.01 pending

Tier anchors

beginner: Sipser 2013 Introduction to the Theory of Computation 3e (Cengage) §8.1-8.2 (the idea of measuring memory instead of time, the class PSPACE as all problems solvable with polynomial memory, and why this class might contain much more than P or NP)
intermediate: Sipser 2013 Introduction to the Theory of Computation 3e (Cengage) §8.1-8.3 (PSPACE, NPSPACE, Savitch's theorem that nondeterministic space $O (f)$ can be simulated in deterministic space $O (f^{2})$ , PSPACE-completeness, and the canonical PSPACE-complete problem TQBF); Arora and Barak 2009 Computational Complexity: A Modern Approach (Cambridge) §4.2-4.3
master: Arora and Barak 2009 Computational Complexity: A Modern Approach (Cambridge) §4.2-4.3 (Savitch's theorem with full proof, PSPACE-completeness, TQBF completeness with the inductive encoding of computation paths, the space hierarchy theorem, and connections to the polynomial hierarchy); Sipser 2013 §8.1-8.3; Papadimitriou 1994 Computational Complexity (Addison-Wesley) §7.2-7.3

References

Sipser, M. — Introduction to the Theory of Computation · Cengage, 3rd edition (2013). §8.1 introduces space complexity by measuring the number of tape cells a Turing machine uses, defines $SPACE (f (n))$ and $NSPACE (f (n))$ as the classes of languages decidable by deterministic and nondeterministic Turing machines using at most $f (n)$ cells on inputs of length $n$ , defines $PSPACE = ⋃_{k} SPACE (n^{k})$ and $NPSPACE = ⋃_{k} NSPACE (n^{k})$ ; §8.1 also observes that $PSPACE \supseteq NP$ since a polynomial-time nondeterministic machine uses at most polynomial space, and states the containment $NP \subseteq PSPACE \subseteq EXPTIME$ ; §8.2 states and proves Savitch's theorem that $NSPACE (f (n)) \subseteq SPACE (f (n)^{2})$ for space-constructible $f \geq lo g n$ , from which $PSPACE = NPSPACE$ follows; §8.3 defines PSPACE-completeness by analogy with NP-completeness, proves that $TQBF = {⟨ ϕ ⟩ : ϕ is a true fully quantified Boolean formula}$ is PSPACE-complete via a recursive Savitch-style evaluation of alternating quantifiers, and surveys further PSPACE-complete problems including the geography game and the problem of deciding winning positions in generalised board games.
Arora, S. and Barak, B. — Computational Complexity: A Modern Approach · Cambridge University Press (2009). §4.2 defines space-bounded computation, introduces the configuration graph of a space-bounded Turing machine — a directed graph whose vertices are configurations (state, head position, non-blank tape contents) and whose edges are single-step transitions — observes that a machine using $S$ cells has at most $2^{O (S)}$ distinct configurations and hence runs in time $2^{O (S)}$ or loops, and defines PSPACE; §4.2 proves Savitch's theorem by showing that reachability in the configuration graph of an $NSPACE (S)$ machine can be tested in $SPACE (S^{2})$ using the recursive predicate $PATH (a, b, t)$ (is there a path of length $\leq 2^{t}$ from $a$ to $b$ ?), which recurs on the midpoint and uses $O (t c d o tS)$ space, giving $NSPACE (S) \subseteq SPACE (S^{2})$ ; §4.3 defines PSPACE-completeness, proves TQBF is PSPACE-complete by encoding the polynomial-space computation as an alternating sequence of existential and universal quantifiers over configurations, and discusses the polynomial hierarchy $PH \subseteq PSPACE$ ; §4.3 also covers the space hierarchy theorem $SPACE (f) ⊊ SPACE (g)$ for $f = o (g)$ .

Estimated time

beginner: 20m
intermediate: 50m
master: 90m