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

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

${\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.

References

• Computational Complexity. Addison Wesley, 1994. (pp 497-498)