EXPSPACE

In computational complexity theory, is the set of all decision problems solvable by a deterministic Turing machine in exponential space, i.e., in $O(2^)$ 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 . If we use a nondeterministic machine instead, we get the class , which is equal to by Savitch's theorem.

A decision problem is if it is in , and every problem in 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. problems might be thought of as the hardest problems in .

is a strict superset of , , and and is believed to be a strict superset of .

Formal definition

In terms of and ,

:$\mathsf = \bigcup_ \mathsf\left(2^\right) = \bigcup_ \mathsf\left(2^\right)$

Examples of problems

An example of an 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).

If the Kleene star is left out, then that problem becomes , which is like , 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 .

Alur and Henzinger extended linear temporal logic with times (integer) and prove that the validity problem of their logic is EXPSPACE-complete.

The coverability problem for Petri Nets is -complete. The reachability problem for Petri nets was known to be -hard for a long time, but shown to be nonelementary, so it is provably not in .

Relationship to other classes

is known to be a strict superset of , , and . It is further suspected to be a strict superset of , however this is not known.

See also

* Game complexity

References

*
* Section 9.1.1: Exponential space completeness, pp. 313–317. Demonstrates that determining equivalence of regular expressions with exponentiation is EXPSPACE-complete.

{{ComplexityClasses

Complexity classes