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 [math]\displaystyle{ 2^{cn} }[/math] for a constant c, and full exponential bounds [math]\displaystyle{ 2^{n^c} }[/math]), 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]
EH
The complexity class EH is the union of the classes [math]\displaystyle{ \Sigma^\mathsf{E}_k }[/math] for all k, where [math]\displaystyle{ \Sigma^\mathsf{E}_k=\mathsf{NE}^{\Sigma^\mathsf{P}_{k-1}} }[/math] (i.e., languages computable in nondeterministic time [math]\displaystyle{ 2^{cn} }[/math] for some constant c with a [math]\displaystyle{ \Sigma^\mathsf{P}_{k-1} }[/math] oracle) and [math]\displaystyle{ \Sigma^\mathsf{E}_0 = \mathsf{E} }[/math]. One also defines
- [math]\displaystyle{ \Pi^\mathsf{E}_k=\mathsf{coNE}^{\Sigma^\mathsf{P}_{k-1}} }[/math] and [math]\displaystyle{ \Delta^\mathsf{E}_k=\mathsf{E}^{\Sigma^\mathsf{P}_{k-1}}. }[/math]
An equivalent definition is that a language L is in [math]\displaystyle{ \Sigma^\mathsf{E}_k }[/math] if and only if it can be written in the form
- [math]\displaystyle{ x\in L\iff\exists y_1\forall y_2\dots Qy_k R(x,y_1,\ldots,y_k), }[/math]
where [math]\displaystyle{ R(x,y_1,\ldots,y_n) }[/math] is a predicate computable in time [math]\displaystyle{ 2^{c|x|} }[/math] (which implicitly bounds the length of yi). Also equivalently, EH is the class of languages computable on an alternating Turing machine in time [math]\displaystyle{ 2^{cn} }[/math] for some c with constantly many alternations.
EXPH
EXPH is the union of the classes [math]\displaystyle{ \Sigma^{\mathsf{EXP}}_k }[/math], where [math]\displaystyle{ \Sigma^{\mathsf{EXP}}_k=\mathsf{NEXP}^{\Sigma^\mathsf{P}_{k-1}} }[/math] (languages computable in nondeterministic time [math]\displaystyle{ 2^{n^c} }[/math] for some constant c with a [math]\displaystyle{ \Sigma^\mathsf{P}_{k-1} }[/math] oracle), [math]\displaystyle{ \Sigma^{\mathsf{EXP}}_0 = \mathsf{EXP} }[/math], and again:
- [math]\displaystyle{ \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]\displaystyle{ \Sigma^{\mathsf{EXP}}_k }[/math] if and only if it can be written as
- [math]\displaystyle{ x\in L\iff\exists y_1 \forall y_2 \dots Qy_k R(x,y_1,\ldots,y_k), }[/math]
where [math]\displaystyle{ R(x,y_1,\ldots,y_k) }[/math] is computable in time [math]\displaystyle{ 2^{|x|^c} }[/math] for some c, which again implicitly bounds the length of yi. Equivalently, EXPH is the class of languages computable in time [math]\displaystyle{ 2^{n^c} }[/math] on an alternating Turing machine with constantly many alternations.
Comparison
References
- ↑ 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.0 2.1 Anuj Dawar, Georg Gottlob, Lauri Hella, Capturing relativized complexity classes without order, Mathematical Logic Quarterly 44 (1998), no. 1, pp. 109–122.
- ↑ Hemachandra, Lane A. (1989). "The strong exponential hierarchy collapses" (in en). Journal of Computer and System Sciences 39 (3): 299–322.
External links
 |  |
