Gerarchia esponenziale

Nella teoria della complessità computazionale, la gerarchia esponenziale è una gerarchia di classi di complessità, che inizia con EXPTIME:

${\displaystyle {\rm {{EXPTIME}=\bigcup _{k\in \mathbb {N} }{\mbox{DTIME}}\left(2^{n^{k}}\right)}}}$

e continua con

${\displaystyle {\mbox{2-EXPTIME}}=\bigcup _{k\in \mathbb {N} }{\mbox{DTIME}}\left(2^{2^{n^{k}}}\right)}$

${\displaystyle {\mbox{3-EXPTIME}}=\bigcup _{k\in \mathbb {N} }{\mbox{DTIME}}\left(2^{2^{2^{n^{k}}}}\right)}$

e così via.

Abbiamo P ⊂ EXPTIME ⊂ 2-EXPTIME ⊂ 3-EXPTIME ⊂ …. Diversamente dal caso analogo della gerarchia polinomiale, il teorema della gerarchia temporale garantisce che queste inclusioni sono corrette; cioè, che vi sono linguaggi in EXPTIME ma non P, in 2-EXPTIME ma non in EXPTIME e così via.

L'unione di tutte le classi nella gerarchia esponenziale è la classe ELEMENTARY.

Bibliografia

• Computational Complexity. Addison Wesley, 1994. (pp 497-498)