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 ${\mathrm{\Sigma }}_k^E$per tot k, on ${\mathrm{\Sigma }}_k^E={\mathrm{N}\mathrm{E}}^{{\mathrm{\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 ${\mathrm{\Sigma }}_{k-1}^P$). Es defineix també ${\mathrm{\Pi }}_k^E={\mathrm{c}\mathrm{o}\mathrm{N}\mathrm{E}}^{{\mathrm{\Sigma }}_{k-1}^P},{\mathrm{\Delta }}_k^E={\mathrm{E}}^{{\mathrm{\Sigma }}_{k-1}^P}$. Una definició equivalent és que un llenguatge L és a ${\mathrm{\Sigma }}_k^E$si i només si es pot escriure de la forma:

$x\in L⟺\mathrm{\exists }{y}_1\mathrm{\forall }{y}_2\dots Q{y}_{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 ${\mathrm{\Sigma }}_k^{EXP}$, on ${\mathrm{\Sigma }}_k^{EXP}={\mathrm{N}\mathrm{E}\mathrm{X}\mathrm{P}}^{{\mathrm{\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 ${\mathrm{\Sigma }}_{k-1}^P$).Es defineix també ${\mathrm{\Pi }}_k^{EXP}={\mathrm{c}\mathrm{o}\mathrm{N}\mathrm{E}\mathrm{X}\mathrm{P}}^{{\mathrm{\Sigma }}_{k-1}^P},{\mathrm{\Delta }}_k^{EXP}={\mathrm{E}\mathrm{X}\mathrm{P}}^{{\mathrm{\Sigma }}_{k-1}^P}$. Una definició equivalent és que un llenguatge L és a ${\mathrm{\Sigma }}_k^E$si i només si es pot escriure de la forma:

$x\in L⟺\mathrm{\exists }{y}_1\mathrm{\forall }{y}_2\dots Q{y}_{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