Gerarchia esponenziale

Da Wikipedia, l'enciclopedia libera.
Se riscontri problemi nella visualizzazione dei caratteri, clicca qui.

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

\rm{EXPTIME} = \bigcup_{k\in\mathbb{N}} \mbox{DTIME}\left(2^{n^k}\right)

e continua con

\mbox{2-EXPTIME} = \bigcup_{k\in\mathbb{N}} \mbox{DTIME}\left(2^{2^{n^k}}\right)
\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[modifica | modifica sorgente]

  • Computational Complexity. Addison Wesley, 1994. (pp 497-498)
matematica Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica