title: 2-EXPTIME
text: # 2-EXPTIME
  
  Nella teoria della complessità computazionale, la classe di complessità 2-EXPTIME (talvolta chiamata 2-EXP, da 2-Exponential Time, "tempo 2-esponenziale") è l'insieme di tutti i problemi decisionali risolvibili da una macchina deterministica di Turing nel tempo $O(2^{2p(n)}),$ dove p(n) è una funzione polinomiale di n.
  
  In termini di DTIME,
  
      ${\mbox{2-EXPTIME}}=\bigcup _{k\in \mathbb {N} }{\mbox{ DTIME }}\left(2^{2^{n^{k}}}\right).$
  
  Sappiamo che
  
      P $\subseteq$ NP $\subseteq$ PSPACE $\subseteq$EXPTIME $\subseteq$ NEXPTIME $\subseteq$ EXPSPACE $\subseteq$ 2-EXPTIME $\subseteq$ ELEMENTARY.
  
  2-EXPTIME può anche essere riformulato come la classe di spazio AEXPSPACE, i problemi che possono essere risolti da una macchina di Turing alternante in spazio esponenziale. Questo è un modo di vedere che EXPSPACE $\subseteq$ 2-EXPTIME, dal momento che una macchina di Turing alternante è potente almeno quanto una macchina deterministica di Turing.
  
  2-EXPTIME è una classe in una gerarchia esponenziale di classi di complessità con limiti temporali sempre più alti. La classe 3-EXPTIME è definita similmente a 2-EXPTIME, ma con un limite temporale triplamente esponenziale $2^{2^{2^{n^{k}}}}$. Questo può essere generalizzato a limiti temporali sempre più alti.
  
  ## Problemi 2-EXPTIME-completi
  
  Le generalizzazioni di molti giochi pienamente osservabili sono EXPTIME-completi. Questi giochi sono visti come un caso particolare di una classe di sistemi di transizione definiti in termini di un insieme di variabili di stato e di azioni/eventi che cambiano i valori delle variabili di stato, insieme alla domanda se esista una strategia vincente.
  
  Una generalizzazione di questa classe di problemi pienamente osservabili a problemi parzialmente osservabili eleva la complessità da EXPTIME-completi a 2-EXPTIME-completi.
  
  