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 with two different meanings (linear exponential bounds 2cn for a constant c, and full exponential bounds 2nc), leading to two versions of the exponential hierarchy.[1][2] These hierarchies are sometimes also referred to as the weak exponential hierarchies, to differentiate them from the strong exponential hierarchy, which contains both of the weak hierarchies.[2][3]

## Contents

* 1 EH
* 2 EXPH
* 3 The strong exponential hierarchy
* 4 Comparison
* 5 References
* 6 External links

## EH

The complexity class EH is the union of the classes ΣkE for all k, where ΣE0=E and ΣkE=NEΣk−1P (i.e., languages computable in nondeterministic time 2cn for some constant c with a Σk−1P oracle). One also defines

ΠkE=coNEΣk−1P and ΔkE=EΣk−1P.

An equivalent definition is that a language L is in ΣkE if and only if it can be written in the form

x∈L⟺∃y1∀y2…QykR(x,y1,…,yk),

where R(x,y1,…,yn) is a predicate computable in time 2c|x| (which implicitly bounds the length of yi). Also equivalently, EH is the class of languages computable on an alternating Turing machine in time 2cn for some c with constantly many alternations.

## EXPH

EXPH is the union of the classes ΣkEXP, where ΣkEXP=NEXPΣk−1P (languages computable in nondeterministic time 2nc for some constant c with a Σk−1P oracle), Σ0EXP=EXP, and again:

ΠkEXP=coNEXPΣk−1P,ΔkEXP=EXPΣk−1P.

A language L is in ΣkEXP if and only if it can be written as

x∈L⟺∃y1∀y2…QykR(x,y1,…,yk),

where R(x,y1,…,yk) 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 2nc on an alternating Turing machine with constantly many alternations.

## The strong exponential hierarchy

The strong exponential hierarchy, denoted SEH, is the union of NE, NPNE, NPNPNE, and so on.[4]

The same class is obtained if we replace NE by NEXP.[4]

## 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. doi:10.1016/0022-0000(89)90025-1.
4. ↑ 4.0 4.1 https://complexityzoo.net/Complexity_Zoo:S#seh

## 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=4227253"
*[v]: View this template
*[t]: Discuss this template
*[e]: Edit this template