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]

## Contents

* 1 EH
* 2 EXPH
* 3 Comparison
* 4 References
* 5 External links

## 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

E ⊆ NE ⊆ EH⊆ ESPACE,
EXP ⊆ NEXP ⊆ EXPH⊆ EXPSPACE,
EH ⊆ EXPH.

## References

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. ↑ 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.
3. ↑ Hemachandra, Lane A. (1989). "The strong exponential hierarchy collapses" (in en). Journal of Computer and System Sciences 39 (3): 299–322.

## External links

Complexity Zoo: Class EH

* v
* t
* e

Important complexity classes (more)

Considered feasible|

* DLOGTIME
* AC0
* ACC0
* TC0
* L
* SL
* RL
* NL
* NC
* SC
* CC
* P
* P-complete
* ZPP
* RP
* BPP
* BQP
* APX

Suspected infeasible|

* UP
* NP
* NP-complete
* NP-hard
* co-NP
* co-NP-complete
* AM
* QMA
* PH
* ⊕P
* PP
* #P
* #P-complete
* IP
* PSPACE
* PSPACE-complete

Considered infeasible|

* EXPTIME
* NEXPTIME
* EXPSPACE
* 2-EXPTIME
* ELEMENTARY
* PR
* R
* RE
* ALL

Class hierarchies|

* Polynomial hierarchy
* Exponential hierarchy
* Grzegorczyk hierarchy
* Arithmetical hierarchy
* Boolean hierarchy

Families of classes|

* DTIME
* NTIME
* DSPACE
* NSPACE
* Probabilistically checkable proof
* Interactive proof system

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Exponential hierarchy. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Exponential_hierarchy&oldid=3377187"
*[v]: View this template
*[t]: Discuss this template
*[e]: Edit this template