Editing Exponential hierarchy

In [[computational complexity theory]], the '''exponential hierarchy''' is a hierarchy of [[complexity class]]es that is an [[EXPTIME|exponential time]] analogue of the [[polynomial hierarchy]]. As elsewhere in complexity theory, “exponential” is used in two different meanings (linear exponential bounds <math>2^{cn}</math> for a constant ''c'', and full exponential bounds <math>2^{n^c}</math>), leading to two versions of the exponential hierarchy.<ref>Sarah Mocas, Separating classes in the exponential-time hierarchy from classes in ''PH'', [[Theoretical Computer Science (journal)|Theoretical Computer Science]] 158 (1996), no.&nbsp;1–2, pp.&nbsp;221–231.</ref><ref name=":0">Anuj Dawar, Georg Gottlob, Lauri Hella, Capturing relativized complexity classes without order, Mathematical Logic Quarterly 44 (1998), no.&nbsp;1, pp.&nbsp;109–122.</ref> This hierarchy is sometimes also referred to as the ''weak'' exponential hierarchy, to differentiate it from the ''strong'' exponential hierarchy.<ref name=":0" /><ref>{{Cite journal|last=Hemachandra|first=Lane A.|date=1989|title=The strong exponential hierarchy collapses|url=|journal=[[Journal of Computer and System Sciences]]|language=en|volume=39|issue=3|pages=299–322|doi=10.1016/0022-0000(89)90025-1}}</ref>

==EH==
The complexity class EH is the union of the classes <math>\Sigma^\mathsf{E}_k</math> for all ''k'', where <math>\Sigma^\mathsf{E}_k=\mathsf{NE}^{\Sigma^\mathsf{P}_{k-1}}</math> (i.e., languages computable in [[nondeterministic Turing machine|nondeterministic]] time <math>2^{cn}</math> for some constant ''c'' with a <math>\Sigma^\mathsf{P}_{k-1}</math> [[oracle Turing machine|oracle]]) and <math>\Sigma^\mathsf{E}_0 = \mathsf{E}</math>. One also defines 

:<math>\Pi^\mathsf{E}_k=\mathsf{coNE}^{\Sigma^\mathsf{P}_{k-1}}</math> and <math>\Delta^\mathsf{E}_k=\mathsf{E}^{\Sigma^\mathsf{P}_{k-1}}.</math>

An equivalent definition is that a language ''L'' is in <math>\Sigma^\mathsf{E}_k</math> if and only if it can be written in the form

:<math>x\in L\iff\exists y_1\forall y_2\dots Qy_k R(x,y_1,\ldots,y_k),</math>

where <math>R(x,y_1,\ldots,y_n)</math> is a predicate computable in time <math>2^{c|x|}</math> (which implicitly bounds the length of ''y<sub>i</sub>''). Also equivalently, EH is the class of languages computable on an [[alternating Turing machine]] in time <math>2^{cn}</math> for some ''c'' with constantly many alternations.

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

:<math>\Pi^{\mathsf{EXP}}_k=\mathsf{coNEXP}^{\Sigma^\mathsf{P}_{k-1}}, \Delta^{\mathsf{EXP}}_k=\mathsf{EXP}^{\Sigma^\mathsf{P}_{k-1}}.</math> 

A language ''L'' is in <math>\Sigma^{\mathsf{EXP}}_k</math> if and only if it can be written as

:<math>x\in L\iff\exists y_1 \forall y_2 \dots Qy_k R(x,y_1,\ldots,y_k),</math>

where <math>R(x,y_1,\ldots,y_k)</math> is computable in time <math>2^{|x|^c}</math> for some ''c'', which again implicitly bounds the length of ''y<sub>i</sub>''. Equivalently, EXPH is the class of languages computable in time <math>2^{n^c}</math> on an alternating Turing machine with constantly many alternations.

==Comparison==

{{Unreferenced section|date=September 2024}}

:[[E (complexity)|E]] ⊆ [[NE (complexity)|NE]] ⊆ EH⊆  [[ESPACE]], 
:[[EXPTIME|EXP]] ⊆ [[NEXPTIME|NEXP]] ⊆ EXPH⊆ [[EXPSPACE]], 
:EH ⊆ EXPH.

== References ==
{{reflist}}

==External links==
{{CZoo|Class EH|E#eh}}

{{ComplexityClasses}}
{{DEFAULTSORT:Exponential Hierarchy}}
[[Category:Complexity classes]]
[[Category:Mathematical logic hierarchies]]