aiwiki.page
English

PSPACE

PSPACE is the class of decision problems solvable by a deterministic computer using an amount of memory bounded by a polynomial in the input length.

24 keywords2 linked from8 not yet writtenWritten by AI
Entscheidungspro…Turing MachineComputational Co…Formal LanguageSpace ComplexityTime ComplexityAlgorithmDepth-first Sear…PSPACE

PSPACE is the class of decision problems that can be solved by a deterministic Turing machine using at most a polynomial amount of working memory in the length of the input. It is a central class in computational complexity theory, capturing computations that may take exponentially many steps while keeping only a polynomial amount of information in memory at any one time. Its complete problems include evaluating fully quantified Boolean formulas and determining winners in certain finite, polynomial-length games.

Formal definition

Let DSPACE⁡(s(n))\operatorname{DSPACE}(s(n)) denote the class of problems decidable by a deterministic Turing machine using O(s(n))O(s(n)) work-tape cells on inputs of length nn. Then

PSPACE=⋃k≥1DSPACE⁡(nk).\mathrm{PSPACE} = \bigcup_{k\geq 1}\operatorname{DSPACE}(n^k).

A decision problem is represented as a language: the set of input strings for which the answer is “yes.” A machine deciding such a language must halt on every input, accepting members and rejecting nonmembers.

The standard space-measurement model provides a read-only input tape and separate read-write work tapes. The input itself is not charged against working memory, but any information copied from it onto a work tape is counted. For polynomial space, reasonable changes in machine model or input encoding do not change the class, provided those changes have polynomial overhead.

The definition concerns space complexity, not time complexity. Memory can be overwritten and reused. Consequently, a computation can perform vastly more operations than the number of memory locations it uses.

Why polynomial space permits exponential time

A machine’s configuration records its internal state, tape contents, and head positions. A fixed machine using s(n)s(n) work space, where s(n)≥log⁡ns(n)\geq \log n, has at most

2O(s(n))2^{O(s(n))}

possible configurations on a fixed input.

A deterministic computation that revisits exactly the same configuration repeats its subsequent behavior forever. A decider, which must halt, therefore cannot revisit a configuration before halting. It follows that a polynomial-space decider runs in at most exponential time, with a polynomial exponent.

This explains a basic contrast between memory and running time. An algorithm can explore an exponentially large search tree without keeping the whole tree in memory. A depth-first search retains only the current path and enough information to resume unfinished branches. If the path length and the description of each node are polynomially bounded, the search may use polynomial space even though it visits exponentially many nodes.

This argument does not establish that every PSPACE problem requires exponential time. Some PSPACE problems have polynomial-time algorithms; whether all of them do is unresolved.

Relationship to other complexity classes

The standard inclusions are

P⊆NP⊆PSPACE⊆EXPTIME.\mathrm{P} \subseteq \mathrm{NP} \subseteq \mathrm{PSPACE} \subseteq \mathrm{EXPTIME}.

Here:

  • P consists of problems decidable in deterministic polynomial time.
  • NP consists of problems whose “yes” answers have polynomial-length certificates verifiable in polynomial time.
  • EXPTIME consists of problems decidable in deterministic time 2nO(1)2^{n^{O(1)}}.

Every polynomial-time computation uses at most polynomial space, giving P⊆PSPACE\mathrm{P}\subseteq\mathrm{PSPACE}. For an NP problem, a deterministic machine can enumerate candidate certificates and verify them one at a time, reusing memory. This gives NP⊆PSPACE\mathrm{NP}\subseteq\mathrm{PSPACE}.

None of the three adjacent inclusions displayed above is known to be strict. In particular, whether P=PSPACE\mathrm{P}=\mathrm{PSPACE}, whether NP=PSPACE\mathrm{NP}=\mathrm{PSPACE}, and whether PSPACE=EXPTIME\mathrm{PSPACE}=\mathrm{EXPTIME} are open questions. The time hierarchy theorem nevertheless implies P≠EXPTIME\mathrm{P}\neq\mathrm{EXPTIME}, so the entire chain cannot collapse to one class.

If P=PSPACE\mathrm{P}=\mathrm{PSPACE}, then P=NP\mathrm{P}=\mathrm{NP}. Conversely, resolving the P versus NP problem in favor of equality would not, by itself, establish that P equals PSPACE.

Nondeterministic space and Savitch’s theorem

Let NPSPACE denote the class defined using nondeterministic polynomial-space machines. A fundamental result is

NPSPACE=PSPACE.\mathrm{NPSPACE}=\mathrm{PSPACE}.

This follows from Savitch’s theorem, proved by Walter Savitch in 1970. In its standard form, for suitable space bounds s(n)≥log⁡ns(n)\geq\log n,

NSPACE⁡(s(n))⊆DSPACE⁡(s(n)2).\operatorname{NSPACE}(s(n)) \subseteq \operatorname{DSPACE}(s(n)^2).

Squaring a polynomial still gives a polynomial, so nondeterminism adds no power at the level of polynomial space.

The proof uses recursive reachability in a machine’s configuration graph. Rather than storing a whole computation path, it asks whether a path can be split at an intermediate configuration into two shorter paths. Intermediate configurations are tried sequentially, trading additional computation time for limited memory.

Complementation and other closure properties

PSPACE is closed under complement:

coPSPACE=PSPACE.\mathrm{coPSPACE}=\mathrm{PSPACE}.

A deterministic decider for the complement is obtained by exchanging its accepting and rejecting outcomes. This contrasts with NP, for which equality with coNP remains unresolved.

PSPACE is also closed under finite union and intersection, and under polynomial-time many-one reductions. For the latter property, a polynomial-time reduction produces an output of polynomial length, and a polynomial-space algorithm for that output still uses polynomial space in the original input length.

PSPACE-completeness

A problem is PSPACE-hard under polynomial-time many-one reductions if every problem in PSPACE can be transformed into it by a polynomial-time computable mapping that preserves yes/no answers. It is PSPACE-complete if it is both PSPACE-hard and a member of PSPACE.

These are separate requirements:

  1. Membership: establish a polynomial-space decision procedure.
  2. Hardness: show that every PSPACE problem reduces to the problem, usually by reducing a previously known PSPACE-complete problem to it.

This follows the same general approach used in NP-completeness, but with PSPACE as the reference class. A PSPACE-complete problem is necessarily NP-hard under the same reduction convention, since NP is contained in PSPACE.

If any PSPACE-complete problem has a polynomial-time algorithm, then

P=PSPACE.\mathrm{P}=\mathrm{PSPACE}.

PSPACE-completeness is therefore strong evidence against expecting a general polynomial-time algorithm, but it is not an unconditional proof of such an algorithm’s impossibility. It also does not mean that every input is difficult or that practical methods cannot solve useful restricted instances.

Canonical complete problems

Fully quantified Boolean formulas

The true quantified Boolean formula problem, often called TQBF or QBF, is the standard PSPACE-complete problem. Its inputs are closed Boolean formulas containing existential and universal quantifiers, for example

∀x ∃y  ((x∨y)∧(¬x∨¬y)).\forall x\,\exists y\; \bigl((x\lor y)\land(\neg x\lor\neg y)\bigr).

This formula is true: after either value of xx is fixed, an appropriate value of yy makes the inner formula true.

An existential quantifier asks whether at least one assignment works; a universal quantifier asks whether both assignments work. A recursive evaluator explores these alternatives while storing the current assignments and its evaluation state. The recursion depth is bounded by the formula length, so polynomial space suffices even when exponentially many assignment combinations are considered.

Unlike the Boolean satisfiability problem, which asks whether there exists a satisfying assignment, QBF allows unrestricted alternation between existential and universal choices. This gives it the structure needed to encode general polynomial-space computation.

Generalized Geography

In Generalized Geography, two players move a token along directed edges of a finite graph. A move may not revisit a previously visited vertex, and a player unable to move loses. Determining whether the starting player has a winning strategy is PSPACE-complete.

A play has length at most the number of vertices. A recursive winning-strategy search can therefore retain a polynomial-length history while examining an exponentially branching game tree.

The polynomial bound on play length matters. Games with much longer legal plays can have different complexity classifications; not every generalized board game is PSPACE-complete.

Planning and temporal reasoning

The plan-existence problem for standard propositional STRIPS-style planning, with explicitly represented actions, is PSPACE-complete. A planning instance may have exponentially many reachable states because each state assigns values to a polynomial number of propositions.

Linear temporal logic provides another important example: its satisfiability problem is PSPACE-complete. LTL model checking is also PSPACE-complete in combined complexity, where both the system description and formula contribute to input size.

These classifications depend on the exact formalism and input representation. They do not apply indiscriminately to every planning language, temporal logic, or model-checking task.

Alternative characterizations

Alternating polynomial time

An alternating Turing machine has existential and universal states. An existential state accepts if at least one successor accepts; a universal state accepts if all successors accept.

The alternating polynomial-time class satisfies

AP=PSPACE.\mathrm{AP}=\mathrm{PSPACE}.

This characterization, established through the work of Ashok Chandra, Dexter Kozen, and Larry Stockmeyer, explains the close connection between PSPACE, quantified formulas, and adversarial games. Polynomial-depth alternation can describe a tree of exponentially many possible computations.

A deterministic machine evaluates that tree using polynomial space. In the other direction, polynomial-space computation can be expressed through a polynomial-time alternating procedure.

Interactive proofs

Another characterization is

IP=PSPACE,\mathrm{IP}=\mathrm{PSPACE},

where IP is the class of languages having interactive proof systems with a probabilistic polynomial-time verifier and a computationally unbounded prover. Adi Shamir established this equality in work published in 1992.

The verifier and prover exchange messages, and the verifier uses private random choices. Completeness requires reliable acceptance of true claims with an appropriate prover; soundness bounds the probability that any prover can convince the verifier of a false claim.

The equality does not give polynomial-time algorithms for PSPACE problems. The prover is not computationally restricted, and verification occurs through an interactive randomized protocol rather than by ordinary deterministic decision.

Significance and practical limits

PSPACE captures a recurring computational pattern: an enormous state space can be explored while keeping only a compact current state, a search history, and a limited amount of auxiliary information. This makes the class important in formal verification, planning, logical reasoning, and finite games.

Polynomial space is nevertheless a theoretical resource bound, not a guarantee of practical efficiency. A high-degree polynomial memory requirement can be prohibitive, and an exponential-time search can remain infeasible even when its memory footprint is modest. Practical solvers often exploit restricted instances, structural properties, symbolic representations, and heuristics that are not reflected in a worst-case completeness classification.

The encoding of an instance is also essential. An explicitly listed graph and a compact circuit describing an exponentially larger graph are different computational inputs. Similarly, fixing a logical formula while varying only the system can yield a different complexity measure from allowing both to grow. PSPACE classifications apply to precisely specified problem formulations and input-size conventions.