In complexity theory, EXPSPACE is the set of all decision problems solvable by a deterministic Turing machine in O(2^{p(n)}) space, where p(n) is a polynomial function of n. (Some authors restrict 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.
In terms of DSPACE and NSPACE,
A decision problem is EXPSPACEcomplete if it is in EXPSPACE, and every problem in EXPSPACE has a polynomialtime manyone reduction to it. In other words, there is a polynomialtime algorithm that transforms instances of one to instances of the other with the same answer. EXPSPACEcomplete problems might be thought of as the hardest problems in EXPSPACE.
EXPSPACE is a strict superset of PSPACE, NP, and P and is believed to be a strict superset of EXPTIME.
An example of an EXPSPACEcomplete problem is the problem of recognizing whether two regular expressions represent different languages, where the expressions are limited to four operators: union, concatenation, the Kleene star (zero or more copies of an expression), and squaring (two copies of an expression).^{[1]}
If the Kleene star is left out, then that problem becomes NEXPTIMEcomplete, which is like EXPTIMEcomplete, except it is defined in terms of nondeterministic Turing machines rather than deterministic.
It has also been shown by L. Berman in 1980 that the problem of verifying/falsifying any firstorder statement about real numbers that involves only addition and comparison (but no multiplication) is in EXPSPACE.
See also
References
 L. Berman The complexity of logical theories, Theoretical Computer Science 11:7178, 1980.
 Michael Sipser (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 053494728X. Section 9.1.1: Exponential space completeness, pp.313–317. Demonstrates that determining equivalence of regular expressions with exponentiation is EXPSPACEcomplete.
Full article ▸
