Exponential hierarchy

In computational complexity theory, the exponential hierarchy is a hierarchy of complexity classes that 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}}${\displaystyle 2^{cn}} for a constant c, and full exponential bounds ${\displaystyle 2^{n^{c}}}${\displaystyle 2^{n^{c}}}), leading to two versions of the exponential hierarchy.^{[1] [2]} This hierarchy is sometimes also referred to as the weak exponential hierarchy, to differentiate it from the strong exponential hierarchy.^{[2] [3]}

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

${\displaystyle \Pi _{k}^{\mathsf {E}}={\mathsf {coNE}}^{\Sigma _{k-1}^{\mathsf {P}}}}${\displaystyle \Pi _{k}^{\mathsf {E}}={\mathsf {coNE}}^{\Sigma _{k-1}^{\mathsf {P}}}} and ${\displaystyle \Delta _{k}^{\mathsf {E}}={\mathsf {E}}^{\Sigma _{k-1}^{\mathsf {P}}}.}${\displaystyle \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}}}${\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}),}${\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})}${\displaystyle R(x,y_{1},\ldots ,y_{n})} is a predicate computable in time ${\displaystyle 2^{c|x|}}${\displaystyle 2^{c|x|}} (which implicitly bounds the length of y_i). Also equivalently, EH is the class of languages computable on an alternating Turing machine in time ${\displaystyle 2^{cn}}${\displaystyle 2^{cn}} for some c with constantly many alternations.

EXPH is the union of the classes ${\displaystyle \Sigma _{k}^{\mathsf {EXP}}}${\displaystyle \Sigma _{k}^{\mathsf {EXP}}}, where ${\displaystyle \Sigma _{k}^{\mathsf {EXP}}={\mathsf {NEXP}}^{\Sigma _{k-1}^{\mathsf {P}}}}${\displaystyle \Sigma _{k}^{\mathsf {EXP}}={\mathsf {NEXP}}^{\Sigma _{k-1}^{\mathsf {P}}}} (languages computable in nondeterministic time ${\displaystyle 2^{n^{c}}}${\displaystyle 2^{n^{c}}} for some constant c with a ${\displaystyle \Sigma _{k-1}^{\mathsf {P}}}${\displaystyle \Sigma _{k-1}^{\mathsf {P}}} oracle), ${\displaystyle \Sigma _{0}^{\mathsf {EXP}}={\mathsf {EXP}}}${\displaystyle \Sigma _{0}^{\mathsf {EXP}}={\mathsf {EXP}}}, 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}}}.}${\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}}}${\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}),}${\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})}${\displaystyle R(x,y_{1},\ldots ,y_{k})} is computable in time ${\displaystyle 2^{|x|^{c}}}${\displaystyle 2^{|x|^{c}}} for some c, which again implicitly bounds the length of y_i. Equivalently, EXPH is the class of languages computable in time ${\displaystyle 2^{n^{c}}}${\displaystyle 2^{n^{c}}} on an alternating Turing machine with constantly many alternations.

E ⊆ NE ⊆ EH⊆ ESPACE,

EXP ⊆ NEXP ⊆ EXPH⊆ EXPSPACE,

EH ⊆ EXPH.

Complexity Zoo : Class EH

• Complexity classes
• Mathematical logic hierarchies

• Articles needing additional references from September 2024
• All articles needing additional references