Jerarquia exponencial

En teoria de la complexitat, la jerarquia exponencial és una jerarquia de classes de complexitat que es l'anàloga a la jerarquia polinòmica amb temps exponencial. En aquest camp, el mot exponencial es fa servir en dos concepte diferents: fites exponencials lineals 2^cn per una c constant i límits exponencials $2^{n^{c}}$, donant dues versions de la jerarquia exponencial:

• EH és la unió de les classes $\Sigma _{k}^{E}$per tot k, on $\Sigma _{k}^{E}=\mathrm {NE} ^{\Sigma _{k-1}^{P}}$(llenguatges computables en una màquina de Turing no determinista en temps 2^cn per alguna constant c amb un oracle $\Sigma _{k-1}^{P}$). Es defineix també $\Pi _{k}^{E}=\mathrm {coNE} ^{\Sigma _{k-1}^{P}},\Delta _{k}^{E}=\mathrm {E} ^{\Sigma _{k-1}^{P}}$. Una definició equivalent és que un llenguatge L és a $\Sigma _{k}^{E}$si i només si es pot escriure de la forma:

$x\in L\iff \exists y_{1}\,\forall y_{2}\dots Qy_{k}\,R(x,y_{1},\dots ,y_{k})$

on $R(x,y_{1},\dots ,y_{n})$és un predicat computable en temps $2^{c|x|}$. També i de forma equivalent, EH és la classe dels llenguatges computables amb una màquina de Turing alternant en temps $2^{cx}$per algun c.

• EHPH és la unió de les classes $\Sigma _{k}^{EXP}$, on $\Sigma _{k}^{EXP}=\mathrm {NEXP} ^{\Sigma _{k-1}^{P}}$(llenguatges computables en una màquina de Turing no determinista en temps $2^{n^{c}}$per alguna constant c amb un oracle $\Sigma _{k-1}^{P}$).Es defineix també $\Pi _{k}^{EXP}=\mathrm {coNEXP} ^{\Sigma _{k-1}^{P}},\Delta _{k}^{EXP}=\mathrm {EXP} ^{\Sigma _{k-1}^{P}}$. Una definició equivalent és que un llenguatge L és a $\Sigma _{k}^{E}$si i només si es pot escriure de la forma:

$x\in L\iff \exists y_{1}\,\forall y_{2}\dots Qy_{k}\,R(x,y_{1},\dots ,y_{k})$

on $R(x,y_{1},\dots ,y_{n})$és un predicat computable en temps $2^{c|x|}$. També i de forma equivalent, EXPH és la classe dels llenguatges computables amb una màquina de Turing alternant en temps $2^{cx}$per algun c.

Es te que E ⊆ NE ⊆ EH ⊆ ESPACE, EXP ⊆ NEXP ⊆ EXPH ⊆ EXPSPACE, i EH ⊆ EXPH.

Vegeu també

• Jerarquia polinòmica
• Jerarquia aritmètica