EXPSPACE

EXPSPACE is a complexity class that contains decision problems solvable by a deterministic Turing machine using at most exponential space, i.e., O(2^p(n)) space for some polynomial p(n), where n is the size of the input. It generalizes PSPACE by allowing space that grows exponentially with respect to the input length but still remains an upper bound. A deterministic machine is required; nondeterministic versions coincide with EXPSPACE due to Savitch's theorem extended to exponential space.

The class is closed under various operations such as union, intersection, complement, and polynomial-time many‑one reductions, mirroring the closure properties of PSPACE. EXPSPACE also equals the class of problems solvable by a deterministic Turing machine in exponential time with logarithmic space, as indicated by the time‑space tradeoff for deterministic machines.

EXPSPACE contains PSPACE and is strictly larger than that class under the widely believed hierarchy conjecture that suggests each level of the exponential time and space hierarchy is strict. It sits below the class NEXPTIME, the nondeterministic counterpart to deterministic exponential time. While NEXPTIME contains EXPSPACE, the separation EXPSPACE≠NEXPTIME remains unproven.

Several natural computational problems are EXPSPACE‑complete. Examples include the word problem for partially commutative monoids, universality for nondeterministic finite automata on succinctly represented input, and determining reachability in succinctly described graphs. These results are established via reductions that preserve the exponential space bound.

Open questions about EXPSPACE involve its precise relationship to classes such as NEXPTIME and the possibility of a polynomial‑time decision procedure for certain subclasses. Additionally, exploring whether EXPSPACE-complete problems admit subexponential deterministic algorithms remains an active research topic.