# Exponential hierarchy

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 ${\displaystyle 2^{cn}}$ for a constant c, and full exponential bounds ${\displaystyle 2^{n^{c}}}$), leading to two versions of the exponential hierarchy.[1][2]

## EH

EH is the union of the classes ${\displaystyle \Sigma _{k}^{\mathsf {E}}}$  for all k, where ${\displaystyle \Sigma _{k}^{\mathsf {E}}={\mathsf {NE}}^{\Sigma _{k-1}^{\mathsf {P}}}}$  (i.e., languages computable in nondeterministic time ${\displaystyle 2^{cn}}$  for some constant c with a ${\displaystyle \Sigma _{k-1}^{\mathsf {P}}}$  oracle). One also defines

${\displaystyle \Pi _{k}^{\mathsf {E}}={\mathsf {coNE}}^{\Sigma _{k-1}^{\mathsf {P}}},\Delta _{k}^{\mathsf {E}}={\mathsf {E}}^{\Sigma _{k-1}^{\mathsf {P}}}.}$

An equivalent definition is that a language L is in ${\displaystyle \Sigma _{k}^{\mathsf {E}}}$  if and only if it can be written in the form

${\displaystyle x\in L\iff \exists y_{1}\forall y_{2}\dots Qy_{k}R(x,y_{1},\ldots ,y_{k}),}$

where ${\displaystyle R(x,y_{1},\ldots ,y_{n})}$  is a predicate computable in time ${\displaystyle 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 ${\displaystyle 2^{cn}}$  for some c with constantly many alternations.

## EXPH

EXPH is the union of the classes ${\displaystyle \Sigma _{k}^{\mathsf {EXP}}}$ , where ${\displaystyle \Sigma _{k}^{\mathsf {EXP}}={\mathsf {NEXP}}^{\Sigma _{k-1}^{\mathsf {P}}}}$  (languages computable in nondeterministic time ${\displaystyle 2^{n^{c}}}$  for some constant c with a ${\displaystyle \Sigma _{k-1}^{\mathsf {P}}}$  oracle), and again:

${\displaystyle \Pi _{k}^{\mathsf {EXP}}={\mathsf {coNEXP}}^{\Sigma _{k-1}^{\mathsf {P}}},\Delta _{k}^{\mathsf {EXP}}={\mathsf {EXP}}^{\Sigma _{k-1}^{\mathsf {P}}}.}$

A language L is in ${\displaystyle \Sigma _{k}^{\mathsf {EXP}}}$  if and only if it can be written as

${\displaystyle x\in L\iff \exists y_{1}\forall y_{2}\dots Qy_{k}R(x,y_{1},\ldots ,y_{k}),}$

where ${\displaystyle R(x,y_{1},\ldots ,y_{k})}$  is computable in time ${\displaystyle 2^{|x|^{c}}}$  for some c, which again implicitly bounds the length of yi. Equivalently, EXPH is the class of languages computable in time ${\displaystyle 2^{n^{c}}}$  on an alternating Turing machine with constantly many alternations.

## Comparison

ENE ⊆ EH ⊆ ESPACE,
EXPNEXP ⊆ EXPH ⊆ EXPSPACE,
EH ⊆ EXPH.

## References

1. ^ Sarah Mocas, Separating classes in the exponential-time hierarchy from classes in PH, Theoretical Computer Science 158 (1996), no. 1–2, pp. 221–231.
2. ^ Anuj Dawar, Georg Gottlob, Lauri Hella, Capturing relativized complexity classes without order, Mathematical Logic Quarterly 44 (1998), no. 1, pp. 109–122.