EXPTIME

Nella teoria della complessità computazionale la classe di complessità EXPTIME (a volte chiamata EXP, da Exponential Time, "tempo esponenziale"), è l'insieme di tutti i problemi decisionali risolvibili da una macchina deterministica di Turing nel tempo O(2^p(n)), dove p(n) è una funzione polinomiale di n.

In termini di DTIME,

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

Sappiamo che

P $\subseteq$ NP $\subseteq$ PSPACE $\subseteq$ EXPTIME $\subseteq$ NEXPTIME $\subseteq$ EXPSPACE

e inoltre, dal teorema della gerarchia temporale e dal teorema della gerarchia spaziale, che

P $\subsetneq$ EXPTIME   e   NP $\subsetneq$ NEXPTIME   e   PSPACE $\subsetneq$ EXPSPACE

così almeno una delle prime tre inclusioni e almeno una delle ultime tre inclusioni deve essere corretta, ma non si sa quali sono, anche se la maggior parte degli esperti credono che tutte le inclusioni siano corrette. Si sa anche che se P = NP, allora EXPTIME = NEXPTIME, la classe dei problemi risolvibili nel tempo esponenziale da una macchina di Turing non deterministica. Più precisamente, EXPTIME ≠ NEXPTIME se e solo se esistono linguaggi sparsi in NP che non sono in P.

EXPTIME può anche essere riformulato come la classe di spazio APSPACE, i problemi che possono essere risolti da una macchina di Turing alternante nello spazio polinomiale. Questo è un modo di vedere che PSPACE $\subseteq$ EXPTIME, poiché una macchina di Turing alternante è potente almeno quanto una macchina di Turing deterministica.

EXPTIME è una classe in una gerarchia esponenziale di classi di complessità con limiti temporali sempre più alti. La classe 2-EXPTIME è definita similmente a EXPTIME, ma con un limite temporale doppiamente esponenziale $2^{2^{n}}$. Questo può essere generalizzato a limiti temporali sempre più alti.

EXPTIME-completo

Un problema decisionale è EXPTIME-completo se è in EXPTIME, e ogni problema in EXPTIME ha una riduzione di tempo polinomiale ad esso. In altre parole, c'è un algoritmo di tempo polinomiale che trasforma richieste dell'uno in richieste dell'altro con la stessa risposta. I Problemi che sono EXPTIME-completi potrebbero essere pensati come i problemi più difficili in EXPTIME. Si noti che sebbene non sappiamo se NP è o no un sottoinsieme di P, sappiamo però che i problemi EXPTIME-completi non sono in P; è stato provato, dal teorema della gerarchia temporale, che questi problemi non possono essere risolti nel tempo polinomiale.

Nella teoria della computabilità, uno dei problemi indecidibili basilari è quello di decidere se una macchina deterministica di Turing (MDT) si arresta. Uno dei più fondamentali problemi EXPTIME-completi p una versione più semplice di questo, che chiede se una MDT si arresta al massimo in k passi. Se è in EXPTIME perché una simulazione banale richiede il tempo O(k), e l'ingresso k è codificato usando O(log k) bit. È EXPTIME-completo perché, parlando all'ingrosso, possiamo usarlo per verificare se una macchina che risolve un problema EXPTIME accetta un numero esponenziale di passi; non ne userà di più. Lo stesso problema con il numero di passi scritto in unario è P-completo.

Altri esempi di problemi EXPTIME-completi includono il problema di valutare una posizione negli scacchi, nella dama, o nel go (con le regole giapponesi del ko) di tipo generalizzato. Questi giochi hanno una probabilità di essere EXPTIME-completi perché i giochi possono durare per un numero di mosse che è esponenziale alla dimensione della scacchiera. Nell'esempio del go, la regola giapponese del ko è sufficientemente intrattabile da implicare la completezza EXPTIME, ma non si sa se le regole più trattabili per il gioco americane o cinesi siano EXPTIME-complete.

Per contrasto, i giochi generalizzati che possono durare per un numero di mosse che è polinomiale alla dimensione della scacchiera sono spesso PSPACE-completi. Lo stesso è vero per i giochi esponenzialmente lunghi in cui la non ripetizione è automatica.

Un altro insieme di importanti problemi EXPTIME-completi si riferisce ai circuiti succinti. I circuiti succinti sono macchine semplici usate per descrivere alcuni grafi in esponenzialmente meno spazio. Essi accettano due numeri di vertice come ingresso e uscita se c'è un margine tra di essi. Per molti problemi di grafi P-completi naturali, dove il grafo è espresso in una rappresentazione naturale come una matrice delle adiacenze, risolvere lo stesso problema su una rappresentazione di un circuito succinto è EXPTIME-completo, perché l'ingresso è esponenzialmente più piccolo; ma questo richiede prove non banali, dal momento che i circuiti succinti possono soltanto descrivere una sottoclasse di grafi.