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