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 ${\displaystyle 2^{n^{c}}}$, donant dues versions de la jerarquia exponencial:^[1][2]

• EH és la unió de les classes ${\displaystyle \Sigma _{k}^{E}}$per tot k, on ${\displaystyle \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 ${\displaystyle \Sigma _{k-1}^{P}}$). Es defineix també ${\displaystyle \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 ${\displaystyle \Sigma _{k}^{E}}$si i només si es pot escriure de la forma:

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

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

• EHPH és la unió de les classes ${\displaystyle \Sigma _{k}^{EXP}}$, on ${\displaystyle \Sigma _{k}^{EXP}=\mathrm {NEXP} ^{\Sigma _{k-1}^{P}}}$(llenguatges computables en una màquina de Turing no determinista en temps ${\displaystyle 2^{n^{c}}}$per alguna constant c amb un oracle ${\displaystyle \Sigma _{k-1}^{P}}$).Es defineix també ${\displaystyle \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 ${\displaystyle \Sigma _{k}^{E}}$si i només si es pot escriure de la forma:

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

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

Es te que E ⊆ NE ⊆ EH ⊆ ESPACE, EXP ⊆ NEXP ⊆ EXPH ⊆ EXPSPACE, i EH ⊆ EXPH.^[3]

Vegeu també

• Jerarquia polinòmica
• Jerarquia aritmètica

Referències