Exponential hierarchy (original) (raw)

From Wikipedia, the free encyclopedia

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 2 c n {\displaystyle 2^{cn}} $2^{cn}$ for a constant c, and full exponential bounds 2 n c {\displaystyle 2^{n^{c}}} $2^{n^{c}}$ ), leading to two versions of the exponential hierarchy.[1][2] This hierarchy is sometimes also referred to as the weak exponential hierarchy, to differentiate it from the strong exponential hierarchy.[2][3]

The complexity class EH is the union of the classes Σ k E {\displaystyle \Sigma _{k}^{\mathsf {E}}} $\Sigma _{k}^{\mathsf {E}}$ for all k, where Σ k E = N E Σ k − 1 P {\displaystyle \Sigma _{k}^{\mathsf {E}}={\mathsf {NE}}^{\Sigma _{k-1}^{\mathsf {P}}}} $\Sigma _{k}^{\mathsf {E}}={\mathsf {NE}}^{\Sigma _{k-1}^{\mathsf {P}}}$ (i.e., languages computable in nondeterministic time 2 c n {\displaystyle 2^{cn}} $2^{cn}$ for some constant c with a Σ k − 1 P {\displaystyle \Sigma _{k-1}^{\mathsf {P}}} $\Sigma _{k-1}^{\mathsf {P}}$ oracle) and Σ 0 E = E {\displaystyle \Sigma _{0}^{\mathsf {E}}={\mathsf {E}}} $\Sigma _{0}^{\mathsf {E}}={\mathsf {E}}$ . One also defines

Π k E = c o N E Σ k − 1 P {\displaystyle \Pi _{k}^{\mathsf {E}}={\mathsf {coNE}}^{\Sigma _{k-1}^{\mathsf {P}}}} $\Pi _{k}^{\mathsf {E}}={\mathsf {coNE}}^{\Sigma _{k-1}^{\mathsf {P}}}$ and Δ k E = E Σ k − 1 P . {\displaystyle \Delta _{k}^{\mathsf {E}}={\mathsf {E}}^{\Sigma _{k-1}^{\mathsf {P}}}.} $\Delta _{k}^{\mathsf {E}}={\mathsf {E}}^{\Sigma _{k-1}^{\mathsf {P}}}.$

An equivalent definition is that a language L is in Σ k E {\displaystyle \Sigma _{k}^{\mathsf {E}}} $\Sigma _{k}^{\mathsf {E}}$ if and only if it can be written in the form

x ∈ L ⟺ ∃ y 1 ∀ y 2 … Q y k R ( x , y 1 , … , y k ) , {\displaystyle x\in L\iff \exists y_{1}\forall y_{2}\dots Qy_{k}R(x,y_{1},\ldots ,y_{k}),} $x\in L\iff \exists y_{1}\forall y_{2}\dots Qy_{k}R(x,y_{1},\ldots ,y_{k}),$

where R ( x , y 1 , … , y n ) {\displaystyle R(x,y_{1},\ldots ,y_{n})} $R(x,y_{1},\ldots ,y_{n})$ is a predicate computable in time 2 c | x | {\displaystyle 2^{c|x|}} $2^{c|x|}$ (which implicitly bounds the length of yi). Also equivalently, EH is the class of languages computable on an alternating Turing machine in time 2 c n {\displaystyle 2^{cn}} $2^{cn}$ for some c with constantly many alternations.

EXPH is the union of the classes Σ k E X P {\displaystyle \Sigma _{k}^{\mathsf {EXP}}} $\Sigma _{k}^{\mathsf {EXP}}$ , where Σ k E X P = N E X P Σ k − 1 P {\displaystyle \Sigma _{k}^{\mathsf {EXP}}={\mathsf {NEXP}}^{\Sigma _{k-1}^{\mathsf {P}}}} $\Sigma _{k}^{\mathsf {EXP}}={\mathsf {NEXP}}^{\Sigma _{k-1}^{\mathsf {P}}}$ (languages computable in nondeterministic time 2 n c {\displaystyle 2^{n^{c}}} $2^{n^{c}}$ for some constant c with a Σ k − 1 P {\displaystyle \Sigma _{k-1}^{\mathsf {P}}} $\Sigma _{k-1}^{\mathsf {P}}$ oracle), Σ 0 E X P = E X P {\displaystyle \Sigma _{0}^{\mathsf {EXP}}={\mathsf {EXP}}} $\Sigma _{0}^{\mathsf {EXP}}={\mathsf {EXP}}$ , and again:

Π k E X P = c o N E X P Σ k − 1 P , Δ k E X P = E X P Σ k − 1 P . {\displaystyle \Pi _{k}^{\mathsf {EXP}}={\mathsf {coNEXP}}^{\Sigma _{k-1}^{\mathsf {P}}},\Delta _{k}^{\mathsf {EXP}}={\mathsf {EXP}}^{\Sigma _{k-1}^{\mathsf {P}}}.} $\Pi _{k}^{\mathsf {EXP}}={\mathsf {coNEXP}}^{\Sigma _{k-1}^{\mathsf {P}}},\Delta _{k}^{\mathsf {EXP}}={\mathsf {EXP}}^{\Sigma _{k-1}^{\mathsf {P}}}.$

A language L is in Σ k E X P {\displaystyle \Sigma _{k}^{\mathsf {EXP}}} $\Sigma _{k}^{\mathsf {EXP}}$ if and only if it can be written as

where R ( x , y 1 , … , y k ) {\displaystyle R(x,y_{1},\ldots ,y_{k})} $R(x,y_{1},\ldots ,y_{k})$ is computable in time 2 | x | c {\displaystyle 2^{|x|^{c}}} $2^{|x|^{c}}$ for some c, which again implicitly bounds the length of yi. Equivalently, EXPH is the class of languages computable in time 2 n c {\displaystyle 2^{n^{c}}} $2^{n^{c}}$ on an alternating Turing machine with constantly many alternations.

E ⊆ NE ⊆ EH⊆ ESPACE,

EXP ⊆ NEXP ⊆ EXPH⊆ EXPSPACE,

EH ⊆ EXPH.

^ Sarah Mocas, Separating classes in the exponential-time hierarchy from classes in PH, Theoretical Computer Science 158 (1996), no. 1–2, pp. 221–231.
^ a b Anuj Dawar, Georg Gottlob, Lauri Hella, Capturing relativized complexity classes without order, Mathematical Logic Quarterly 44 (1998), no. 1, pp. 109–122.
^ Hemachandra, Lane A. (1989). "The strong exponential hierarchy collapses". Journal of Computer and System Sciences. 39 (3): 299–322. doi:10.1016/0022-0000(89)90025-1.

Complexity Zoo: Class EH