PSPACE

Uses your system voice; voice and rate in settings.

Snapshot

≈ 1 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.

, 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 polynomial amount of space.

, 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 polynomial amount of space. \mathsf{PSPACE} = \bigcup_{k\in\mathbb{N}} \mathsf{SPACE}(n^k). It turns out that allowing the Turing machine to be nondeterministic does not add any extra power. Because of Savitch's theorem, \mathsf{NPSPACE} is equivalent to \mathsf{PSPACE} , 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. Also, the complements of all problems in \mathsf{PSPACE} are also in \mathsf{PSPACE} , meaning that \mathsf{coPSPACE}=\mathsf{PSPACE} .

Further reading

Chapter 19: Polynomial space, pp. 455–490. Chapter 8: Space Complexity

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

Provenance

snapshot enwiki-001358371398 · captured 1780896762.0 · version history

Cite this page as: encyclopegia.org, “PSPACE”, snapshot enwiki-001358371398. https://encyclopegia.org/a/pspace

Sources cited in this revision

1 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.