2-EXPTIME

In computational complexity theory, the complexity class2-EXPTIME (sometimes called 2-EXP, sometimes also written 2EXPTIME) is the set of all decision problems solvable by a deterministic Turing machine in O(2^2p(n)) time, where p(n) is a polynomial function of n.

In terms of DTIME,

${\displaystyle {\mathsf {2{\mbox{-}}EXPTIME}}=\bigcup _{k\in \mathbb {N} }{\mathsf {DTIME}}\left(2^{2^{n^{k}}}\right).}$

We know

P ⊆ NP ⊆ PSPACE ⊆ EXPTIME ⊆ NEXPTIME ⊆ EXPSPACE ⊆ 2-EXPTIME ⊆ ELEMENTARY.

2-EXPTIME can also be reformulated as the space class AEXPSPACE, the problems that can be solved by an alternating Turing machine in exponential space. This is one way to see that EXPSPACE ⊆ 2-EXPTIME, since an alternating Turing machine is at least as powerful as a deterministic Turing machine.^[1]

2-EXPTIME is one class in a hierarchy of complexity classes with increasingly higher time bounds. The class 3-EXPTIME is defined similarly to 2-EXPTIME but with a triply exponential time bound ${\displaystyle 2^{2^{2^{n^{k}}}}}$. This can be generalized to higher and higher time bounds.

Examples of algorithms that require at least double-exponential time include:

• Each decision procedure for Presburger arithmetic provably requires at least doubly exponential time^[2]
• Computing a Gröbner basis over a field. In the worst case, a Gröbner basis may have a number of elements which is doubly exponential in the number of variables. On the other hand, the worst-case complexity of Gröbner basis algorithms is doubly exponential in the number of variables as well as in the entry size.^[3]
• Finding a complete set of associative-commutative unifiers^[4]
• Quantifier elimination on real closed fields takes doubly exponential time (see Cylindrical algebraic decomposition). Thus, deciding whether a first-order formula over the real numbers is in 2-EXPTIME. But it was shown to be EXPSPACE and was conjectured to be EXPSPACE-complete in 1986.^[5]
• Calculating the complement of a regular expression^[6]

• 二重指数関数