In computational complexity theory, the exponential hierarchy is a hierarchy of complexity classes that is an exponential time analogue of the polynomial hierarchy for a constant c), leading to two versions of the exponential hierarchy. 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.

EH

for all k, where \Sigma^\mathsf{E}_0 = \mathsf{E} (i.e., languages computable in nondeterministic for some constant c oracle). One also defines

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

(which implicitly bounds the length of yi). Also equivalently, EH is the class of languages computable on an alternating Turing machine for some c with constantly many alternations.

EXPH

for some constant c, and again:

A language L if and only if it can be written as

for some c, which again implicitly bounds the length of yi 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.

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

Comparison

1. E ⊆ NE ⊆ EH⊆ ESPACE,

2. EXP ⊆ NEXP ⊆ EXPH⊆ EXPSPACE,

3. EH ⊆ EXPH.

References

External links