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 ${\displaystyle O(2^{p(n)})}$ space, where ${\displaystyle p(n)}$ is a polynomial function of ${\displaystyle n}$. Some authors restrict ${\displaystyle 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,

${\displaystyle {\mathsf {EXPSPACE}}=\bigcup _{k\in \mathbb {N} }{\mathsf {DSPACE}}\left(2^{n^{k}}\right)=\bigcup _{k\in \mathbb {N} }{\mathsf {NSPACE}}\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).^[1]

Logic

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

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

Petri nets

The coverability problem for Petri Nets is EXPSPACE-complete.^[4]

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

See also

• Game complexity