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 y_i). 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 y_i. 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

E ⊆ NE ⊆ EH⊆ ESPACE,

EXP ⊆ NEXP ⊆ EXPH⊆ EXPSPACE,

EH ⊆ EXPH.

References

External links

Complexity Zoo: Class EH

0.00 (0 votes) Original source: https://en.wikipedia.org/wiki/Exponential hierarchy. Read more