PSPACE

, NP, co-NP, BPP, P/poly, PH, and PSPACE {{unsolved|computer science|{{tmath|\mathsf{P \overset{?} PSPACE} }}}} In computational complexity theory, PSPACE is the set of all decision problems that can be solved by a Turing machine using a…

Uses your system voice; voice and rate in settings.

Snapshot

≈ 6 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

In computational complexity theory, PSPACE is the set of all decision problems that can be solved by a Turing machine using a polynomial amount of space.

Formal definition

edit edit source

If we denote by 𝖲𝖯𝖠𝖢𝖤(f(n)) the set of all problems that can be solved by Turing machines using O(f(n)) space for some function f of the input size n, then we can define 𝖯𝖲𝖯𝖠𝖢𝖤 formally as[1]

𝖯𝖲𝖯𝖠𝖢𝖤=⋃k∈ℕ𝖲𝖯𝖠𝖢𝖤(nk).

It turns out that allowing the Turing machine to be nondeterministic does not add any extra power. Because of Savitch's theorem,[2] 𝖭𝖯𝖲𝖯𝖠𝖢𝖤 is equivalent to 𝖯𝖲𝖯𝖠𝖢𝖤, because a deterministic Turing machine can simulate a nondeterministic Turing machine while roughly squaring the amount of space, and squaring takes polynomials to (bigger) polynomials.[3] Also, the complements of all problems in 𝖯𝖲𝖯𝖠𝖢𝖤 are also in 𝖯𝖲𝖯𝖠𝖢𝖤, meaning that 𝖼𝗈𝖯𝖲𝖯𝖠𝖢𝖤=𝖯𝖲𝖯𝖠𝖢𝖤.[4]

Relation among other classes

edit edit source

The following relations are known between PSPACE and the complexity classes NL, P, NP, PH, EXPTIME and EXPSPACE (we use here ⊂ to denote strict containment, meaning a proper subset, whereas ⊆ includes the possibility that the two sets are the same):

𝖭𝖫⊆𝖯⊆𝖭𝖯⊆𝖯𝖧⊆𝖯𝖲𝖯𝖠𝖢𝖤𝖯𝖲𝖯𝖠𝖢𝖤⊆𝖤𝖷𝖯𝖳𝖨𝖬𝖤⊆𝖤𝖷𝖯𝖲𝖯𝖠𝖢𝖤𝖭𝖫⊂𝖯𝖲𝖯𝖠𝖢𝖤⊂𝖤𝖷𝖯𝖲𝖯𝖠𝖢𝖤𝖯⊂𝖤𝖷𝖯𝖳𝖨𝖬𝖤

From the third line, it follows that both in the first and in the second line, at least one of the set containments must be strict, but it is not known which. It is widely suspected that all are strict.

The containments in the third line are both known to be strict. The first follows from direct diagonalization (the space hierarchy theorem, NL ⊂ NPSPACE) and the fact that PSPACE = NPSPACE via Savitch's theorem. The second follows simply from the space hierarchy theorem.

The hardest problems in PSPACE are the PSPACE-complete problems. See PSPACE-complete for examples of problems that are suspected to be in PSPACE but not in NP.

Closure properties

edit edit source

The class PSPACE is closed under operations union, complementation, and Kleene star.

Other characterizations

edit edit source

An alternative characterization of PSPACE is the set of problems decidable by an alternating Turing machine in polynomial time, sometimes called APTIME or just AP.[5]

A logical characterization of PSPACE from descriptive complexity theory is that it is the set of problems expressible in second-order logic with the addition of a transitive closure operator. A full transitive closure is not needed; a commutative transitive closure and even weaker forms suffice. It is the addition of this operator that (possibly) distinguishes PSPACE from PH.

A major result of complexity theory is that PSPACE can be characterized as all the languages recognizable by a particular interactive proof system, the one defining the class IP. In this system, there is an all-powerful prover trying to convince a randomized polynomial-time verifier that a string is in the language. It should be able to convince the verifier with high probability if the string is in the language, but should not be able to convince it except with low probability if the string is not in the language.

PSPACE can be characterized as the quantum complexity class QIP.[6]

PSPACE is also equal to PCTC, problems solvable by classical computers using closed timelike curves,[7] as well as to BQPCTC, problems solvable by quantum computers using closed timelike curves.[8]

PSPACE-completeness

edit edit source

A language B is PSPACE-complete if it is in PSPACE and it is PSPACE-hard, which means for all A ∈ PSPACE, A≤PB, where A≤PB means that there is a polynomial-time many-one reduction from A to B. PSPACE-complete problems are of great importance to studying PSPACE problems because they represent the most difficult problems in PSPACE. Finding a simple solution to a PSPACE-complete problem would mean we have a simple solution to all other problems in PSPACE because all PSPACE problems could be reduced to a PSPACE-complete problem.[9]

An example of a PSPACE-complete problem is the quantified Boolean formula problem (usually abbreviated to QBF or TQBF; the T stands for "true").[9]

Notes

edit edit source
  1. ^ Arora & Barak (2009) p.81 Wikipedia revision 1358371398, retrieved 2026-11-19
  2. ^ Arora & Barak (2009) p.85 Wikipedia revision 1358371398, retrieved 2026-11-19
  3. ^ Arora & Barak (2009) p.86 Wikipedia revision 1358371398, retrieved 2026-11-19
  4. ^ Motwani, Rajeev; Raghavan, Prabhakar (1995). Randomized Algorithms. Cambridge University Press. p. 20. ISBN 9780521474658. Wikipedia revision 1358371398, retrieved 2026-11-19
  5. ^ Arora & Barak (2009) p.100 Wikipedia revision 1358371398, retrieved 2026-11-19
  6. ^ Rahul Jain; Zhengfeng Ji; Sarvagya Upadhyay; John Watrous (July 2009). "QIP = PSPACE". arXiv:0907.4737 [quant-ph]. Wikipedia revision 1358371398, retrieved 2026-11-19
  7. ^ S. Aaronson (March 2005). "NP-complete problems and physical reality". SIGACT News. arXiv:quant-ph/0502072. Bibcode:2005quant.ph..2072A. doi:10.1145/1052796.1052804. S2CID 18759797.. Wikipedia revision 1358371398, retrieved 2026-11-19
  8. ^ Watrous, John; Aaronson, Scott (2009). "Closed timelike curves make quantum and classical computing equivalent". Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences. 465 (2102): 631. arXiv:0808.2669. Bibcode:2009RSPSA.465..631A. doi:10.1098/rspa.2008.0350. S2CID 745646. Wikipedia revision 1358371398, retrieved 2026-11-19
  9. ^ a b Arora & Barak (2009) p.83 Wikipedia revision 1358371398, retrieved 2026-11-19

References

edit edit source

Further reading

edit edit source Complexity classesConsidered feasible Suspected infeasible Considered infeasible Other complexity classes Class hierarchies Families of classes List of complexity classes

Text derived from https://en.wikipedia.org/w/index.php?oldid=1358371398 under CC BY-SA 4.0; modifications have been made.