# EXPSPACE

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 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 and is believed to be a strict superset of EXPTIME.

An example of an EXPSPACE-complete 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 NEXPTIME-complete, which is like EXPTIME-complete, except it is defined in terms of non-deterministic Turing machines rather than deterministic.

It has also been shown by L. Berman in 1980 that the problem of verifying/falsifying any first-order statement about real numbers that involves only addition and comparison (but no multiplication) is in EXPSPACE.

## See also

## References

- ↑ Meyer, A.R. and L. Stockmeyer. The equivalence problem for regular expressions with squaring requires exponential space.
*13th IEEE Symposium on Switching and Automata Theory*, Oct 1972, pp.125–129.

- L. Berman
*The complexity of logical theories*, Theoretical Computer Science 11:71-78, 1980. - 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.