EXPSPACE

In computational complexity theory, EXPSPACE is the set of all decision problems solvable by a deterministic Turing machine in exponential space, i.e., in ${\displaystyle O(2^{p(n)})}$ space, where ${\displaystyle p(n)}$ is a polynomial function of ${\displaystyle n}$. Some authors restrict ${\displaystyle p(n)}$ to be a linear function, but most authors instead call the resulting class ESPACE. If we use a nondeterministic machine instead, we get the class NEXPSPACE, which is equal to EXPSPACE by Savitch's theorem.

A decision problem is EXPSPACE-complete if it is in EXPSPACE, and every problem in EXPSPACE has a polynomial-time many-one reduction to it. In other words, there is a polynomial-time algorithm that transforms instances of one to instances of the other with the same answer. EXPSPACE-complete problems might be thought of as the hardest problems in EXPSPACE.

EXPSPACE is a strict superset of PSPACE, NP, and P. It contains EXPTIME and is believed to strictly contain it, but this is unproven.

Formal definition

In terms of DSPACE and NSPACE,

${\displaystyle {\mathsf {EXPSPACE}}=\bigcup _{k\in \mathbb {N} }{\mathsf {DSPACE}}\left(2^{n^{k}}\right)=\bigcup _{k\in \mathbb {N} }{\mathsf {NSPACE}}\left(2^{n^{k}}\right)}$

Examples of problems

See also

• Game complexity

References

• Berman, Leonard (1 May 1980). "The complexity of logical theories". Theoretical Computer Science. 11 (1): 71–77. doi:10.1016/0304-3975(80)90037-7.
• Michael Sipser (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X. Section 9.1.1: Exponential space completeness, pp. 313–317. Demonstrates that determining equivalence of regular expressions with exponentiation is EXPSPACE-complete.