Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Exponential hierarchy
open-in-new
<h2 id="eh">EH</h2> <p>The complexity class EH is the union of the classes Σ k E {\displaystyle \Sigma _{k}^{\mathsf {E}}} for all <i>k</i>, where Σ k E = N E Σ k − 1 P {\displaystyle \Sigma _{k}^{\mathsf {E}}={\mathsf {NE}}^{\Sigma _{k-1}^{\mathsf {P}}}} (i.e., languages computable in <a href="/facts/Nondeterministic_Turing_machine/zv2x6XPG">nondeterministic</a> time 2 c n {\displaystyle 2^{cn}} for some constant <i>c</i> with a Σ k − 1 P {\displaystyle \Sigma _{k-1}^{\mathsf {P}}} <a href="/facts/Oracle_Turing_machine/6ScMuvvY">oracle</a>) and Σ 0 E = E {\displaystyle \Sigma _{0}^{\mathsf {E}}={\mathsf {E}}} . One also defines </p> Π k E = c o N E Σ k − 1 P {\displaystyle \Pi _{k}^{\mathsf {E}}={\mathsf {coNE}}^{\Sigma _{k-1}^{\mathsf {P}}}} and Δ k E = E Σ k − 1 P . {\displaystyle \Delta _{k}^{\mathsf {E}}={\mathsf {E}}^{\Sigma _{k-1}^{\mathsf {P}}}.} <p>An equivalent definition is that a language <i>L</i> is in Σ k E {\displaystyle \Sigma _{k}^{\mathsf {E}}} if and only if it can be written in the form </p> x ∈ L ⟺ ∃ y 1 ∀ y 2 … Q y k R ( x , y 1 , … , y k ) , {\displaystyle x\in L\iff \exists y_{1}\forall y_{2}\dots Qy_{k}R(x,y_{1},\ldots ,y_{k}),} <p>where R ( x , y 1 , … , y n ) {\displaystyle R(x,y_{1},\ldots ,y_{n})} is a predicate computable in time 2 c | x | {\displaystyle 2^{c|x|}} (which implicitly bounds the length of <i>yi</i>). Also equivalently, EH is the class of languages computable on an <a href="/facts/Alternating_Turing_machine/WktK7ADY">alternating Turing machine</a> in time 2 c n {\displaystyle 2^{cn}} for some <i>c</i> with constantly many alternations. </p> <h2 id="exph">EXPH</h2> <p>EXPH is the union of the classes Σ k E X P {\displaystyle \Sigma _{k}^{\mathsf {EXP}}} , where Σ k E X P = N E X P Σ k − 1 P {\displaystyle \Sigma _{k}^{\mathsf {EXP}}={\mathsf {NEXP}}^{\Sigma _{k-1}^{\mathsf {P}}}} (languages computable in nondeterministic time 2 n c {\displaystyle 2^{n^{c}}} for some constant <i>c</i> with a Σ k − 1 P {\displaystyle \Sigma _{k-1}^{\mathsf {P}}} oracle), Σ 0 E X P = E X P {\displaystyle \Sigma _{0}^{\mathsf {EXP}}={\mathsf {EXP}}} , and again: </p> Π k E X P = c o N E X P Σ k − 1 P , Δ k E X P = E X P Σ k − 1 P . {\displaystyle \Pi _{k}^{\mathsf {EXP}}={\mathsf {coNEXP}}^{\Sigma _{k-1}^{\mathsf {P}}},\Delta _{k}^{\mathsf {EXP}}={\mathsf {EXP}}^{\Sigma _{k-1}^{\mathsf {P}}}.} <p>A language <i>L</i> is in Σ k E X P {\displaystyle \Sigma _{k}^{\mathsf {EXP}}} if and only if it can be written as </p> x ∈ L ⟺ ∃ y 1 ∀ y 2 … Q y k R ( x , y 1 , … , y k ) , {\displaystyle x\in L\iff \exists y_{1}\forall y_{2}\dots Qy_{k}R(x,y_{1},\ldots ,y_{k}),} <p>where R ( x , y 1 , … , y k ) {\displaystyle R(x,y_{1},\ldots ,y_{k})} is computable in time 2 | x | c {\displaystyle 2^{|x|^{c}}} for some <i>c</i>, which again implicitly bounds the length of <i>yi</i>. Equivalently, EXPH is the class of languages computable in time 2 n c {\displaystyle 2^{n^{c}}} on an alternating Turing machine with constantly many alternations. </p> <h2 id="comparison">Comparison</h2> <a href="/facts/E_(complexity)/c3gskbGb">E</a> ⊆ <a href="/facts/NE_(complexity)/PGxsCM70">NE</a> ⊆ EH⊆ <a href="/facts/ESPACE/4P0DCzVg">ESPACE</a>, <a href="/facts/EXPTIME/GbTmY8t5">EXP</a> ⊆ <a href="/facts/NEXPTIME/2pghWvBV">NEXP</a> ⊆ EXPH⊆ <a href="/facts/EXPSPACE/Qkkhx0fr">EXPSPACE</a>, EH ⊆ EXPH. <h2 id="external-links">External links</h2> <p><i><a href="/facts/Complexity_Zoo/htGK5zuz">Complexity Zoo</a></i>: <a href="https://complexityzoo.net/Complexity_Zoo:E#eh">Class EH</a> </p> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>Sarah Mocas, Separating classes in the exponential-time hierarchy from classes in PH, Theoretical Computer Science 158 (1996), no. 1–2, pp. 221–231. <a href="/wiki/Theoretical_Computer_Science_(journal)" target="_blank">/wiki/Theoretical_Computer_Science_(journal)</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>Anuj Dawar, Georg Gottlob, Lauri Hella, Capturing relativized complexity classes without order, Mathematical Logic Quarterly 44 (1998), no. 1, pp. 109–122. <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> <li id="fn:3"><p>Anuj Dawar, Georg Gottlob, Lauri Hella, Capturing relativized complexity classes without order, Mathematical Logic Quarterly 44 (1998), no. 1, pp. 109–122. <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li> <li id="fn:4"><p>Hemachandra, Lane A. (1989). "The strong exponential hierarchy collapses". Journal of Computer and System Sciences. 39 (3): 299–322. doi:10.1016/0022-0000(89)90025-1. <a href="/wiki/Journal_of_Computer_and_System_Sciences" target="_blank">/wiki/Journal_of_Computer_and_System_Sciences</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li> </ol>