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 that are 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 hierarchy is the class ELEMENTARY.

References

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