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

References

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