Wikipedia

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 (linear exponential bounds for a constant c, and full exponential bounds ), leading to two versions of the exponential hierarchy.[1][2]

EH

EH is the union of the classes for all k, where (i.e., languages computable in nondeterministic time for some constant c with a oracle). 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 (which implicitly bounds the length of yi). 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 (languages computable in nondeterministic time for some constant c with a oracle), 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

ENE ⊆ EH ⊆ ESPACE,
EXPNEXP ⊆ 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. ^ Anuj Dawar, Georg Gottlob, Lauri Hella, Capturing relativized complexity classes without order, Mathematical Logic Quarterly 44 (1998), no. 1, pp. 109–122.

External links

Complexity Zoo: Class EH

This article is copied from an article on Wikipedia® - the free encyclopedia created and edited by its online user community. The text was not checked or edited by anyone on our staff. Although the vast majority of Wikipedia® encyclopedia articles provide accurate and timely information, please do not assume the accuracy of any particular article. This article is distributed under the terms of GNU Free Documentation License.

Copyright © 2003-2025 Farlex, Inc Disclaimer
All content on this website, including dictionary, thesaurus, literature, geography, and other reference data is for informational purposes only. This information should not be considered complete, up to date, and is not intended to be used in place of a visit, consultation, or advice of a legal, medical, or any other professional.