Exponential hierarchy

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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

  • EH is the union of the classes \Sigma^E_k for all k, where \Sigma^E_k=\mathrm{NE}^{\Sigma^P_{k-1}} (i.e., languages computable in nondeterministic time 2^{cn} for some constant c with a \Sigma^P_{k-1} oracle). One also defines \Pi^E_k=\mathrm{coNE}^{\Sigma^P_{k-1}}, \Delta^E_k=\mathrm E^{\Sigma^P_{k-1}}. An equivalent definition is that a language L is in \Sigma^E_k if and only if it can be written in the form
x\in L\iff\exists y_1\,\forall y_2\dots Qy_k\,R(x,y_1,\dots,y_k),
where R(x,y_1,\dots,y_n) is a predicate computable in time 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 2^{cn} for some c with constantly many alternations.
  • EXPH is the union of the classes \Sigma^{EXP}_k, where \Sigma^{EXP}_k=\mathrm{NEXP}^{\Sigma^P_{k-1}} (languages computable in nondeterministic time 2^{n^c} for some constant c with a \Sigma^P_{k-1} oracle), and again \Pi^{EXP}_k=\mathrm{coNEXP}^{\Sigma^P_{k-1}}, \Delta^{EXP}_k=\mathrm{EXP}^{\Sigma^P_{k-1}}. A language L is in \Sigma^{EXP}_k if and only if it can be written as
x\in L\iff\exists y_1\,\forall y_2\dots Qy_k\,R(x,y_1,\dots,y_k),
where R(x,y_1,\dots,y_k) is computable in time 2^{|x|^c} for some c, which again implicitly bounds the length of yi. Equivalently, EXPH is the class of languages computable in time 2^{n^c} on an alternating Turing machine with constantly many alternations.

We have ENE ⊆ EH ⊆ ESPACE, EXPNEXP ⊆ EXPH ⊆ EXPSPACE, and EH ⊆ EXPH.

References[edit]

  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.

External links[edit]

Complexity Zoo: Class EH