PSPACE-complete
complexity class
In computational complexity theory, a decision problem is PSPACE-complete if it can be solved using an amount of memory that is polynomial in the input length (polynomial space) and if every other problem that can be solved in polynomial space can be transformed to it in polynomial time. The problems that are PSPACE-complete can be thought of as the hardest problems in PSPACE, the class of decision problems solvable in polynomial space, because a solution to any one such problem could easily be used to solve any other problem in PSPACE.
Problems known to be PSPACE-complete include determining properties of regular expressions and context-sensitive grammars, determining the truth of quantified Boolean formulas, step-by-step changes between solutions of combinatorial optimization problems, and many puzzles and games.
Theory
A problem is defined to be PSPACE-complete if it can be solved using a polynomial amount of memory (it belongs to PSPACE) and every problem in PSPACE can be transformed in polynomial time into an equivalent instance of the given problem.
The PSPACE-complete problems are widely suspected to be outside the more famous complexity classes P (polynomial time) and NP (non-deterministic polynomial time), but that is not known. It is known that they lie outside of the class NC, a class of problems with highly efficient parallel algorithms, because problems in NC can be solved in an amount of space polynomial in the logarithm of the input size, and the class of problems solvable in such a small amount of space is strictly contained in PSPACE by the space hierarchy theorem.
The transformations that are usually considered in defining PSPACE-completeness are polynomial-time many-one reductions, transformations that take a single instance of a problem of one type into an equivalent single instance of a problem of a different type. However, it is also possible to define completeness using Turing reductions, in which one problem can be solved in a polynomial number of calls to a subroutine for the other problem. It is not known whether these two types of reductions lead to different classes of PSPACE-complete problems. Other types of reductions, such as many-one reductions that always increase the length of the transformed input, have also been considered.
A version of the Berman–Hartmanis conjecture for PSPACE-complete sets states that all such sets look alike, in the sense that they can all be transformed into each other by polynomial-time bijections.
The public source identifies “PSPACE-complete” as complexity class. This brief keeps that definition visible, then builds a research path around PSPACE-complete, complexity and class.
Why this record matters
A short description can identify a subject without explaining its stakes. For “PSPACE-complete”, the useful work is to connect “complexity class” to the records capable of establishing context and consequence.
Named sources, stable identifiers and responsible institutions provide the strongest route from overview to verifiable evidence. The source revision retrieved here is dated Jan 2, 2026. The linked authority identifier is Q905967. None of the 0 selected statements returned an explicit reference.
Overview language is designed for orientation and should not be treated as a substitute for the evidence cited beneath it. The source lead contains qualifying language; that uncertainty should survive quotation, summary and reuse. Authority statements aid reconciliation but still require their own references, qualifiers and ranks to be checked.
How to read it
Use the entry as an orientation point, then follow its citations and revision history. Names, dates and institutional relationships should be checked against the original record.
- Subject orientation
- Search vocabulary
- Locating named sources
The closest primary source, responsible institution and strongest cited specialist reference.
Three-step research path
- Establish the record: confirm the title “PSPACE-complete”, its source revision and the description used here.
- Expand the search: follow PSPACE-complete primary sources, PSPACE-complete archive and PSPACE-complete research across catalogues and specialist indexes.
- Test the account: compare the strongest cited source with the responsible institution’s current record and note any disagreement.
Questions for further research
- Which source most directly establishes the central claim about “PSPACE-complete”?
- Which institution is responsible for the underlying evidence?
- What terminology or title could unlock a more precise catalogue search?
Search terms from this dossier
This entry incorporates text from “PSPACE-complete” on English Wikipedia. Contributors are listed in the page history. Text is available under the Creative Commons Attribution-ShareAlike 4.0 License. Selected authority identifiers and statements are retrieved from Wikidata under CC0; their references and qualifiers remain part of the verification path.