Editing Exponential hierarchy (section)

==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.