Exponential hierarchy


In computational complexity theory, the exponential hierarchy is a hierarchy of complexity classes, which is an exponential time analogue of the polynomial hierarchy. As elsewhere in complexity theory, “exponential” is used in two different meanings, leading to two versions of the exponential hierarchy.

EH

EH is the union of the classes for all k, where . One also defines
An equivalent definition is that a language L is in if and only if it can be written in the form
where is a predicate computable in time . Also equivalently, EH is the class of languages computable on an alternating Turing machine in time for some c with constantly many alternations.

EXPH

EXPH is the union of the classes, where , and again:
A language L is in if and only if it can be written as
where is computable in time for some c, which again implicitly bounds the length of yi. Equivalently, EXPH is the class of languages computable in time on an alternating Turing machine with constantly many alternations.

Comparison