Proper noun
The set of all decision problems that can be solved by a Turing machine using O(2ᵖ⁽ⁿ⁾) units of memory, where p(n) is a polynomial function of the input size.
- Examples
-
First, the hierarchy theorems tell us that a Turing machine can decide more languages in EXPSPACE than it can in PSPACE.