EXPSPACE

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

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.

Formal definition

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)$

Examples of problems

Formal languages

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

Logic

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

Reasoning in the first-order theory of the real numbers with +, ×, = is in EXPSPACE and was conjectured to be EXPSPACE-complete in 1986.

Petri nets

Main article: Petri net

The coverability problem for Petri Nets is EXPSPACE-complete.

The reachability problem for Petri nets was known to be EXPSPACE-hard for a long time, but shown to be nonelementary, so probably not in EXPSPACE. In 2022 it was shown to be Ackermann-complete.

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.