GeezerVison

In computational complexity theory, EXPSPACE is the set of all decision problems solvable by a deterministic Turing machine in exponential space, i.e., in $O\left(2^{p\left(n\right)}\right)$ space, where $p\left(n\right)$ is a polynomial function of $n$. Some authors restrict $p\left(n\right)$ 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.

In terms of DSPACE and NSPACE,

$𝖤𝖷𝖯𝖲𝖯𝖠𝖢𝖤=\bigcup _{k\in \mathbb{N}}𝖣𝖲𝖯𝖠𝖢𝖤\left(2^{n^k}\right)=\bigcup _{k\in \mathbb{N}}𝖭𝖲𝖯𝖠𝖢𝖤\left(2^{n^k}\right)$

• Game complexity

• 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.