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>2^{cn}</math> for a constant c, and full exponential bounds <math>2^{n^c}</math>), leading to two versions of the exponential hierarchy.<ref>Sarah Mocas, Separating classes in the exponential-time hierarchy from classes in PH, Theoretical Computer Science 158 (1996), no. 1–2, pp. 221–231.</ref><ref name=":0">Anuj Dawar, Georg Gottlob, Lauri Hella, Capturing relativized complexity classes without order, Mathematical Logic Quarterly 44 (1998), no. 1, pp. 109–122.</ref> This hierarchy is sometimes also referred to as the weak exponential hierarchy, to differentiate it from the strong exponential hierarchy.<ref name=":0" /><ref>Template:Cite journal</ref>

EH

The complexity class EH is the union of the classes <math>\Sigma^\mathsf{E}_k</math> for all k, where <math>\Sigma^\mathsf{E}_k=\mathsf{NE}^{\Sigma^\mathsf{P}_{k-1}}</math> (i.e., languages computable in nondeterministic time <math>2^{cn}</math> for some constant c with a <math>\Sigma^\mathsf{P}_{k-1}</math> oracle) and <math>\Sigma^\mathsf{E}_0 = \mathsf{E}</math>. One also defines

<math>\Pi^\mathsf{E}_k=\mathsf{coNE}^{\Sigma^\mathsf{P}_{k-1}}</math> and <math>\Delta^\mathsf{E}_k=\mathsf{E}^{\Sigma^\mathsf{P}_{k-1}}.</math>

An equivalent definition is that a language L is in <math>\Sigma^\mathsf{E}_k</math> if and only if it can be written in the form

<math>x\in L\iff\exists y_1\forall y_2\dots Qy_k R(x,y_1,\ldots,y_k),</math>

where <math>R(x,y_1,\ldots,y_n)</math> is a predicate computable in time <math>2^{c|x|}</math> (which implicitly bounds the length of y_i). Also equivalently, EH is the class of languages computable on an alternating Turing machine in time <math>2^{cn}</math> for some c with constantly many alternations.

EXPH

EXPH is the union of the classes <math>\Sigma^{\mathsf{EXP}}_k</math>, where <math>\Sigma^{\mathsf{EXP}}_k=\mathsf{NEXP}^{\Sigma^\mathsf{P}_{k-1}}</math> (languages computable in nondeterministic time <math>2^{n^c}</math> for some constant c with a <math>\Sigma^\mathsf{P}_{k-1}</math> oracle), <math>\Sigma^{\mathsf{EXP}}_0 = \mathsf{EXP}</math>, and again:

<math>\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>\Sigma^{\mathsf{EXP}}_k</math> if and only if it can be written as

<math>x\in L\iff\exists y_1 \forall y_2 \dots Qy_k R(x,y_1,\ldots,y_k),</math>

where <math>R(x,y_1,\ldots,y_k)</math> is computable in time <math>2^{|x|^c}</math> for some c, which again implicitly bounds the length of y_i. Equivalently, EXPH is the class of languages computable in time <math>2^{n^c}</math> on an alternating Turing machine with constantly many alternations.

Comparison

{{ safesubst:#invoke:Unsubst||date=__DATE__ |$B= {{ safesubst:#invoke:Unsubst||date=__DATE__ |$B= Template:Ambox }} }}

E ⊆ NE ⊆ EH⊆ ESPACE,

EXP ⊆ NEXP ⊆ EXPH⊆ EXPSPACE,

EH ⊆ EXPH.