# PSPACE

**PSPACE** is the complexity class of decision problems that can be decided by a deterministic [Turing machine](https://www.edgepedia.org/turing-machine) using an amount of memory (tape space) bounded by a polynomial in the input length, regardless of how long the computation takes. It is defined as the union of the classes SPACE(n^k) over all k, and its nondeterministic counterpart NPSPACE turns out to be equal to it by Savitch's theorem.<sup>[1](https://courses.cs.washington.edu/courses/cse431/25wi/notes/lectures-19-20.pdf)</sup>

| Key fact | Detail |
|---|---|
| Definition | \( \mathrm{PSPACE} = \bigcup_{k} \mathrm{SPACE}(n^k) \), the languages decidable by a deterministic Turing machine in polynomial space<sup>[1](https://courses.cs.washington.edu/courses/cse431/25wi/notes/lectures-19-20.pdf)</sup> |
| Nondeterminism | Savitch's theorem (1970): for \( S(n) \geq \log n \), \( \mathrm{NSPACE}(S(n)) \subseteq \mathrm{SPACE}(S(n)^2) \), so PSPACE = NPSPACE<sup>[1](https://courses.cs.washington.edu/courses/cse431/25wi/notes/lectures-19-20.pdf)</sup> |
| Known containments | \( \mathrm{P} \subseteq \mathrm{NP} \subseteq \mathrm{PSPACE} \subseteq \mathrm{EXPTIME} \)<sup>[2](https://ac.informatik.uni-freiburg.de/teaching/ss_16/tcs/lecturenotes.pdf)</sup> |
| Complete problem | TQBF, the set of true fully quantified Boolean formulas, is PSPACE-complete (Meyer–Stockmeyer)<sup>[3](https://people.csail.mit.edu/rrw/6.1400-2025/lec22-color.pdf)</sup> |
| Strict separations | By the Space Hierarchy Theorem, L ≠ PSPACE ≠ EXPSPACE<sup>[4](https://courses.csail.mit.edu/6.892/spring19/lectures/L01.html)</sup> |
| Open question | Whether P = PSPACE is unknown; it is not even known how to prove P ≠ PSPACE<sup>[5](https://ocw.mit.edu/courses/18-404j-theory-of-computation-fall-2020/3a37f978045d4293c204cbcb72c6573a_cT_qwkTigv4.pdf)</sup> |

## Definition

Space complexity is measured with a machine model in which the input tape is read-only and only the work tape is charged for space: SPACE(S(n)) is the set of languages decided by a deterministic machine using O(S(n)) work-tape cells, and NSPACE(S(n)) is defined the same way for nondeterministic machines, counting the maximum cells used on any computation path.<sup>[1](https://courses.cs.washington.edu/courses/cse431/25wi/notes/lectures-19-20.pdf)</sup> PSPACE is then the union of SPACE(n^k) over all k, and NPSPACE the union of NSPACE(n^k).<sup>[1](https://courses.cs.washington.edu/courses/cse431/25wi/notes/lectures-19-20.pdf)</sup> The definition requires the machine to be a decider that halts on every input; a machine that loops forever while using little space does not contribute its language to the class.<sup>[5](https://ocw.mit.edu/courses/18-404j-theory-of-computation-fall-2020/3a37f978045d4293c204cbcb72c6573a_cT_qwkTigv4.pdf)</sup>

The class is robust to the machine model. Converting a multi-tape machine to a one-tape machine increases the space used by only a linear factor, so the same class PSPACE results whether space is defined for one-tape or multi-tape machines.<sup>[5](https://ocw.mit.edu/courses/18-404j-theory-of-computation-fall-2020/3a37f978045d4293c204cbcb72c6573a_cT_qwkTigv4.pdf)</sup>

## Relation to time classes

A machine that runs in T(n) time can visit at most T(n) tape cells, so TIME(T(n)) ⊆ SPACE(T(n)) and NTIME(T(n)) ⊆ SPACE(T(n)); this gives P ⊆ PSPACE and NP ⊆ PSPACE directly.<sup>[1](https://courses.cs.washington.edu/courses/cse431/25wi/notes/lectures-19-20.pdf)</sup><sup> • </sup><sup>[2](https://ac.informatik.uni-freiburg.de/teaching/ss_16/tcs/lecturenotes.pdf)</sup> The inclusion NP ⊆ PSPACE can also be seen through certificates: for a language in NP, a polynomial-space algorithm can consecutively generate all (exponentially many) candidate certificates and run the polynomial-time verifier on each, reusing the same space every time.<sup>[2](https://ac.informatik.uni-freiburg.de/teaching/ss_16/tcs/lecturenotes.pdf)</sup>

Conversely, a machine using O(S(n)) space has at most \( n \cdot 2^{O(S(n))} \) possible configurations, since the input head has n positions, the work-tape head O(S(n)) positions, the work-tape contents \( 2^{O(S(n))} \) possibilities, and the state O(1) possibilities. For \( S(n) \geq \log n \) this is \( 2^{O(S(n))} \) configurations, so SPACE(S(n)) ⊆ TIME(2^{O(S(n))}) and the same for NSPACE; in particular PSPACE ⊆ EXPTIME.<sup>[1](https://courses.cs.washington.edu/courses/cse431/25wi/notes/lectures-19-20.pdf)</sup><sup> • </sup><sup>[6](https://homes.cs.aau.dk/~srba/courses/slides-CC-10/l14-2x3.pdf)</sup> A decider can never repeat a configuration without looping, so its running time is bounded by the number of configurations.<sup>[6](https://homes.cs.aau.dk/~srba/courses/slides-CC-10/l14-2x3.pdf)</sup>

A concrete example shows why space is a weaker requirement than time: SAT is decidable in SPACE(n) by copying the formula to the work tape and iterating through all assignments, reusing the same space for each one; this takes exponential time but only linear space.<sup>[1](https://courses.cs.washington.edu/courses/cse431/25wi/notes/lectures-19-20.pdf)</sup>

## Savitch's theorem

The naive way to simulate a nondeterministic space-S(n) machine deterministically is to explore its whole computation tree, but that tree can have \( 2^{2^{O(S(n))}} \) leaves, far more than the \( 2^{O(S(n))} \) distinct configurations.<sup>[1](https://courses.cs.washington.edu/courses/cse431/25wi/notes/lectures-19-20.pdf)</sup> Savitch's theorem, proved by Walter J. Savitch in 1970 in the Journal of Computer and System Sciences, does better: for \( S(n) \geq \log n \), \( \mathrm{NSPACE}(S(n)) \subseteq \mathrm{SPACE}(S(n)^2) \).<sup>[1](https://courses.cs.washington.edu/courses/cse431/25wi/notes/lectures-19-20.pdf)</sup><sup> • </sup><sup>[7](https://pages.cs.wisc.edu/~dieter/Papers/r-ul-eccc.pdf)</sup>

The proof views the machine's configurations as a directed graph whose vertices are configurations and whose edges are single machine steps; the machine accepts exactly when the accepting configuration is reachable from the start configuration.<sup>[1](https://courses.cs.washington.edu/courses/cse431/25wi/notes/lectures-19-20.pdf)</sup> A recursive procedure CANYIELD tests whether configuration D is reachable from configuration C within t steps by trying each possible midpoint configuration and recursing on both halves, \( \mathrm{CANYIELD}_t(C,D) = 1 \iff \exists C_{\mathrm{mid}} \) with both halves reachable in t/2 steps. The recursion depth is O(S(n)) and each level stores a constant number of configurations, giving the quadratic space bound while reusing space across recursive calls.<sup>[1](https://courses.cs.washington.edu/courses/cse431/25wi/notes/lectures-19-20.pdf)</sup> Since squaring a polynomial is still a polynomial, NPSPACE = PSPACE.<sup>[2](https://ac.informatik.uni-freiburg.de/teaching/ss_16/tcs/lecturenotes.pdf)</sup> This contrasts with the time setting, where whether nondeterministic polynomial time equals deterministic polynomial time (P versus NP) is open.<sup>[5](https://ocw.mit.edu/courses/18-404j-theory-of-computation-fall-2020/3a37f978045d4293c204cbcb72c6573a_cT_qwkTigv4.pdf)</sup>

## Complete problems

A language B is PSPACE-complete if B is in PSPACE and every language in PSPACE is polynomial-time reducible to B.<sup>[3](https://people.csail.mit.edu/rrw/6.1400-2025/lec22-color.pdf)</sup> The canonical example is TQBF, the set of true fully quantified Boolean formulas, in which every variable is bound by an existential (∃) or universal (∀) quantifier at the front of the formula. Meyer and Stockmeyer proved TQBF is PSPACE-complete; SAT is the special case in which all quantifiers are existential, and TAUTOLOGY the special case in which all are universal.<sup>[3](https://people.csail.mit.edu/rrw/6.1400-2025/lec22-color.pdf)</sup> TQBF is in PSPACE because a recursive solver can set one quantified variable at a time to 0 and then 1, reusing space across the two recursive calls, accepting for ∃ if at least one branch accepts and for ∀ if both do.<sup>[3](https://people.csail.mit.edu/rrw/6.1400-2025/lec22-color.pdf)</sup>

The decision problem for quantified Boolean formulas is generally viewed as the archetype of PSPACE-completeness, and QBF serves as an encoding framework for problems in artificial intelligence and formal verification, including planning, model checking, non-monotonic reasoning, and reactive synthesis.<sup>[8](https://iris.uniss.it/handle/11388/239898?mode=complete)</sup><sup> • </sup><sup>[9](https://arxiv.org/abs/2405.06485)</sup> Games are another source: generalized geography was proved PSPACE-complete by Thomas Schaefer in 1978 via a reduction from quantified Boolean formulas, and puzzles such as Rush Hour are PSPACE-complete.<sup>[10](https://www.combinatorial-game-theory.com/essays/pspace-completeness/)</sup><sup> • </sup><sup>[4](https://courses.csail.mit.edu/6.892/spring19/lectures/L01.html)</sup>

## Characterizations and structure

**Alternation.** Chandra, Kozen, and Stockmeyer introduced alternating Turing machines, a generalization of nondeterminism in which existential and universal states alternate. They proved that alternating polynomial time equals deterministic polynomial space, that is \( \mathrm{ATIME}[n^{O(1)}] = \mathrm{PSPACE} \), and that alternating polynomial space equals deterministic exponential time.<sup>[11](https://research.ibm.com/publications/alternation)</sup>

**Closure and hierarchy.** PSPACE is closed under complement because it is defined in terms of deterministic machines, whose accept and reject behavior can be flipped; hence coNP ⊆ PSPACE as well.<sup>[5](https://ocw.mit.edu/courses/18-404j-theory-of-computation-fall-2020/3a37f978045d4293c204cbcb72c6573a_cT_qwkTigv4.pdf)</sup> The Space Hierarchy Theorem shows that more space strictly buys more computing power: for space-constructible bounds, DSPACE(t(n)) is strictly contained in DSPACE(s(n)) whenever t(n) grows asymptotically slower than s(n). This yields the known strict separations L ≠ PSPACE and PSPACE ≠ [EXPSPACE](https://www.edgepedia.org/expspace).<sup>[12](https://encyclopediaofmath.org/wiki/PSPACE)</sup><sup> • </sup><sup>[4](https://courses.csail.mit.edu/6.892/spring19/lectures/L01.html)</sup>

**What remains open.** The chain \( \mathrm{P} \subseteq \mathrm{NP} \subseteq \mathrm{PSPACE} \) contains at least one strict inclusion, because P ≠ EXPTIME by the time hierarchy and PSPACE ⊆ EXPTIME, but which inclusions are strict is unknown; in particular, whether P = PSPACE is an open problem, and no proof of P ≠ PSPACE is known even though PSPACE appears to be a far larger class.<sup>[2](https://ac.informatik.uni-freiburg.de/teaching/ss_16/tcs/lecturenotes.pdf)</sup><sup> • </sup><sup>[5](https://ocw.mit.edu/courses/18-404j-theory-of-computation-fall-2020/3a37f978045d4293c204cbcb72c6573a_cT_qwkTigv4.pdf)</sup> Savitch's theorem likewise leaves open whether the quadratic blowup in space when removing nondeterminism is necessary.<sup>[13](https://cs.uwaterloo.ca/~eblais/cs365/w26/space)</sup>

## References

1. [CSE 431, Lectures 19–20: Space Complexity, Savitch's Theorem, University of Washington](https://courses.cs.washington.edu/courses/cse431/25wi/notes/lectures-19-20.pdf)
2. [Theoretical Computer Science II, Lecture notes, University of Freiburg](https://ac.informatik.uni-freiburg.de/teaching/ss_16/tcs/lecturenotes.pdf)
3. [MIT 6.1400, Lecture 22: Complexity, TQBF is PSPACE-complete](https://people.csail.mit.edu/rrw/6.1400-2025/lec22-color.pdf)
4. [MIT 6.892, Lecture 1: Algorithmic Lower Bounds, Spring 2019](https://courses.csail.mit.edu/6.892/spring19/lectures/L01.html)
5. [MIT 18.404, Lecture 17 transcript: Space Complexity, PSPACE, Savitch's Theorem](https://ocw.mit.edu/courses/18-404j-theory-of-computation-fall-2020/3a37f978045d4293c204cbcb72c6573a_cT_qwkTigv4.pdf)
6. [Computability and Complexity, Lecture 14: Time and Space Complexity, Aalborg University](https://homes.cs.aau.dk/~srba/courses/slides-CC-10/l14-2x3.pdf)
7. [W. J. Savitch (1970). Relationships between nondeterministic and deterministic tape complexities. Journal of Computer and System Sciences 4(2):177–192](https://pages.cs.wisc.edu/~dieter/Papers/r-ul-eccc.pdf)
8. [Shukla, Biere, Pulina, Seidl (2019). A survey on applications of quantified boolean formulas](https://iris.uniss.it/handle/11388/239898?mode=complete)
9. [Eriksson et al. (2024). Solving Quantified Boolean Formulas with Few Existential Variables, arXiv](https://arxiv.org/abs/2405.06485)
10. [Combinatorial Game Theory: Hard, proved (PSPACE-completeness of games)](https://www.combinatorial-game-theory.com/essays/pspace-completeness/)
11. [Chandra, Kozen, Stockmeyer (1981). Alternation. Journal of the ACM, IBM Research](https://research.ibm.com/publications/alternation)
12. [Computational complexity classes, Encyclopedia of Mathematics](https://encyclopediaofmath.org/wiki/PSPACE)
13. [CS 365, Space Complexity, University of Waterloo](https://cs.uwaterloo.ca/~eblais/cs365/w26/space)

---
*Topic: Encyclopedia › Physical world and mathematics › Mathematics and statistics › Logic and discrete mathematics › General discrete mathematics and discrete structures › Computability theory › Models of computation and computability formalisms*

*Initially written Sep 17, 2026 · Reviewed: Oct 15, 2026 · Edited: Oct 15, 2026 · Last review: Oct 15, 2026*

*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*

License: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license