✳flâneur — a map of the web's best reading

PSPACE - Wikipedia

en.wikipedia.org · 1,362 words · saved by 1 readers

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. If we denote by SPACE(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 PSPACE formally as[1] PSPACE is a strict superset of the set of context-sensitive languages.[citation needed] It turns out that allowing the Turing machine to be nondeterministic does not add any extra power. Because of Savitch's theorem,[2] NPSPACE is equivalent to PSPACE, essentially because a deterministic Turing machine can simulate a nondeterministic Turing machine without needing much more space (even though it may use much more time).[3] Also, the complements of all problems in PSPACE are also in PSPACE, meaning that co-PSPACE = PSPACE. The following relations are known between PSPACE and the complexity classes NL, P, NP, PH, EXPTIME and EXPSPACE (note that ⊊,

PSPACE - Wikipedia Jump to content From Wikipedia, the free encyclopedia Class of computational complexity Not to be confused with P-space . "Polynomial space" redirects here. For spaces of polynomials, see Polynomial ring . Inclusions of complexity classes including P , NP , co-NP , BPP , P/poly , PH , and PSPACE Unsolved problem in computer science ⁠ P = ? P S P A C E {\displaystyle {\mathsf {P{\overset {?}{=}}PSPACE}}} ⁠ More unsolved problems in computer science In computational complexity theory , PSPACE is the set of all decision problems that can be solved by a Turing machine using a po

Explore this link on the map →

related reading