Math 2.0

Computer science Definition

PSPACE-completeness

Builds on PSPACEPolynomial-time reductionFormal languagePNP

Definition

Let Σ\Sigma be a finite alphabet, and let C⊆Σ∗C \subseteq \Sigma^* be a language. The language CC is PSPACE-complete when both conditions hold.

  1. CC lies in the class PSPACE.
  2. A≤pCA \le_p C for every A∈PSPACEA \in \mathrm{PSPACE}, where ≤p\le_p is polynomial-time reducibility.

A language that satisfies condition 2 is called PSPACE-hard.

Remarks

Example: the language TQBF of true fully quantified Boolean formulas, such as ∀x ∃y (x∨y)∧(¬x∨¬y)\forall x \, \exists y \, (x \lor y) \land (\neg x \lor \neg y), is PSPACE-complete. It lies in PSPACE because a recursive evaluation over the quantifiers reuses space and needs space polynomial in the formula. Hardness comes from encoding a polynomial-space computation by a quantified formula.

Non-example: the empty language lies in PSPACE but fails condition 2. Only the empty language reduces to it, while PSPACE contains nonempty languages.

Other PSPACE-complete problems are generalized geography and the universality of regular expressions, which asks whether a regular expression describes all strings. If a PSPACE-complete language lies in P, then P=PSPACE\mathrm{P} = \mathrm{PSPACE}. If one lies in NP, then NP=PSPACE\mathrm{NP} = \mathrm{PSPACE}.

Reading path

To understand this page from the ground up, read these 6 pages in order. The foundations come first.

Show the path as a graph
Formal language, concept, no evidence levelFormal languageconceptNP, concept, no evidence levelNPconceptP, concept, no evidence levelPconceptPSPACE, concept, no evidence levelPSPACEconceptPolynomial-time reduction, concept, no evidence levelPolynomial-time reduc…conceptPSPACE-completeness, definition, no evidence levelPSPACE-completenessdefinition
Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.
  • no evidence level
  1. Formal language concept
  2. NP concept
  3. P concept
  4. PSPACE concept
  5. Polynomial-time reduction concept
  6. PSPACE-completeness definition

Further reading

  1. Web https://en.wikipedia.org/wiki/PSPACE-complete
About this page
TagVTMF1QTZ9R
URIm2://VTMF1QTZ9R
Kinddefinition
WritingW0 stub
MSC68Q17, 68Q15
DefinesPSPACE-completeness
UsesPSPACE, Polynomial-time reduction, Formal language, P, NP
Changed3 November 2026

Markdown · JSON · Edit on GitHub

What this page needs for W1

  • an inventory row: the row of the inventory that the node accounts for (0 of 1)
  • a source with a locator (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

No page links to this page yet.