In computational complexity theory, the exponential hierarchy is a hierarchy of complexity classes, which is an exponential time analogue of the polynomial hierarchy. As elsewhere in complexity theory, “exponential” is used in two different meanings (linear exponential bounds 2 c n for a constant c, and full exponential bounds 2 n c ), leading to two versions of the exponential hierarchy:
EH is the union of the classes Σ k E for all k, where Σ k E = N E Σ k − 1 P (i.e., languages computable in nondeterministic time 2 c n for some constant c with a Σ k − 1 P oracle). One also defines Π k E = c o N E Σ k − 1 P , Δ k E = E Σ k − 1 P . An equivalent definition is that a language L is in Σ k E if and only if it can be written in the formwhere
R ( x , y 1 , … , y n ) is a predicate computable in time
2 c | x | (which implicitly bounds the length of
yi). Also equivalently, EH is the class of languages computable on an
alternating Turing machine in time
2 c n for some
c with constantly many alternations.
EXPH is the union of the classes Σ k E X P , where Σ k E X P = N E X P Σ k − 1 P (languages computable in nondeterministic time 2 n c for some constant c with a Σ k − 1 P oracle), and again Π k E X P = c o N E X P Σ k − 1 P , Δ k E X P = E X P Σ k − 1 P . A language L is in Σ k E X P if and only if it can be written aswhere
R ( x , y 1 , … , y k ) is computable in time
2 | x | c for some
c, which again implicitly bounds the length of
yi. Equivalently, EXPH is the class of languages computable in time
2 n c on an alternating Turing machine with constantly many alternations.
We have E ⊆ NE ⊆ EH ⊆ ESPACE, EXP ⊆ NEXP ⊆ EXPH ⊆ EXPSPACE, and EH ⊆ EXPH.
