PSPACE Complexity Class

Graduate Depth 73 in the knowledge graph I know this Set as goal
Unlocks 5 downstream topics
complexity-classes space-bounded

Core Idea

PSPACE is the class of decision problems solvable by a deterministic Turing machine in polynomial space. A key result (Savitch's theorem) shows PSPACE = NPSPACE, contrasting sharply with the P vs NP question. PSPACE strictly contains NP and is believed strictly larger than P, though both containments are unproven. PSPACE-complete problems include TQBF (true quantified Boolean formulas) and game-position evaluation, representing problems intractable by polynomial time but feasible with polynomial space.

Explainer

From your study of space complexity classes, you know that computational resources can be measured in space (tape cells used) rather than time (steps taken). PSPACE is the class of all decision problems solvable using a polynomial amount of memory, with no restriction on how long the computation takes. This is a powerful resource model: a machine with polynomial space can run for exponential time (since it can cycle through exponentially many configurations before repeating a state), making PSPACE a very large class.

The most striking fact about PSPACE is Savitch's theorem: any problem solvable by a nondeterministic Turing machine in polynomial space can also be solved by a deterministic machine in polynomial space. In other words, PSPACE = NPSPACE. This stands in sharp contrast to the time-bounded world, where the question of whether nondeterminism helps (P vs NP) remains open. The intuition behind Savitch's theorem is that space can be reused — a deterministic machine can systematically explore all nondeterministic branches one at a time, reusing the same memory for each branch, at the cost of taking much longer.

The known containment chain is P ⊆ NP ⊆ PSPACE ⊆ EXPTIME. Every polynomial-time problem uses at most polynomial space (you cannot write to more cells than you have steps), so P ⊆ PSPACE. Every NP problem can be solved in PSPACE by deterministically trying all possible certificates. We believe all these containments are strict — that PSPACE is genuinely larger than NP and P — but no separation has been proven between P and PSPACE. We do know that P ≠ EXPTIME (by the time hierarchy theorem), which means at least one of these containments is strict.

The canonical PSPACE-complete problem is TQBF (True Quantified Boolean Formulas): given a fully quantified Boolean formula with alternating "for all" and "there exists" quantifiers, determine whether it is true. The alternation of quantifiers is what makes TQBF harder than SAT — it captures the back-and-forth reasoning of two-player games. This is why evaluating game positions (generalized chess, Go on an n×n board) tends to be PSPACE-complete: determining whether a player has a winning strategy requires reasoning about all possible opponent responses to all possible moves, a structure naturally expressed with quantifier alternation.

Practice Questions 5 questions

Prerequisite Chain

Counting to 10Counting to 20Understanding ZeroThe Number ZeroCounting to FiveOne-to-One CorrespondenceCombining Small Groups Within 5Addition Within 10Addition Within 20Two-Digit Addition Without RegroupingTwo-Digit Addition with RegroupingAddition Within 100Repeated Addition as MultiplicationMultiplication Facts Within 100Division as Equal SharingDivision as Grouping (Measurement Division)Division: Grouping (Repeated Subtraction) ModelDivision: Fair Sharing ModelDivision as Equal SharingDivision as GroupingBasic Division FactsDivision Facts Within 100Two-Digit by One-Digit DivisionDivision with RemaindersRemainders and Quotients in DivisionDivision Word ProblemsIntroduction to Long DivisionFactors and MultiplesPrime and Composite NumbersEquivalent FractionsRelating Fractions and DecimalsDecimal Place ValueReading and Writing DecimalsComparing and Ordering DecimalsAdding and Subtracting DecimalsMultiplying DecimalsDividing DecimalsDividing FractionsMixed Number ArithmeticOrder of OperationsInteger Order of OperationsVariable ExpressionsCombining Like TermsOne-Step EquationsTwo-Step EquationsSolving Multi-Step EquationsEquations with Variables on Both SidesLiteral EquationsSlope-Intercept FormPoint-Slope FormWriting Linear EquationsParallel and Perpendicular Line SlopesGraphing Linear EquationsPiecewise FunctionsStep FunctionsComposition of FunctionsInverse FunctionsRadical Functions and GraphsRational ExponentsExponential Functions and GraphsLogarithms IntroductionTime and Space ComplexityTime Complexity Classes: P and EXPTIMENondeterministic Time Complexity and NPThe P vs. NP ProblemComplexity Class P: Polynomial TimeComplexity Class NP: Nondeterministic Polynomial TimeNP-Completeness and Cook-Levin TheoremThe Cook-Levin TheoremBoolean Satisfiability, Cook-Levin, and ReductionsPolynomial Many-One ReductionsBPP: Bounded Error Probabilistic Polynomial TimeRP and coRP Complexity ClassesPSPACE Complexity Class

Longest path: 74 steps · 376 total prerequisite topics

Prerequisites (4)

Leads To (2)