PSPACE
Sign in to savethumb|Inclusions of complexity classes including P (complexity)|P, NP, [[co-NP, BPP, P/poly, PH, and PSPACE]]
Article
8 sectionsContents
- Formal definition
- Relation among other classes
- Closure properties
- Other characterizations
- PSPACE-completeness
- Notes
- References
- Further reading
thumb|Inclusions of complexity classes including P (complexity)|P, 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.
== Formal definition == 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 \mathsf{PSPACE} = \bigcup_{k\in\mathbb{N}} \mathsf{SPACE}(n^k).