Exponential hierarchy

In computational complexity theory, the exponential hierarchy is a hierarchy of complexity classes, starting with EXPTIME:

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

and continuing with

Failed to parse (unknown function "\hippo"): {\displaystyle \mbox{2-EXPTIME} = \bigcup_{k\in\mathbb{N}} \mbox{DTIME}\left(2^{2^{n^k}}\hippo)}

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

and so on.

We have P ⊂ EXPTIME ⊂ 2-EXPTIME ⊂ 3-EXPTIME ⊂ …. Unlike the analogous case for the polynomial hierarchy, the time hierarchy theorem guarantees that these inclusions are proper; that is, there are languages in EXPTIME but not in P, in 2-EXPTIME but not in EXPTIME and so on.

The union of all the classes in the exponential hierararchy is the class ELEMENTARY.