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,

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

Sappiamo che

P ${\displaystyle \subseteq }$ NP ${\displaystyle \subseteq }$ PSPACE ${\displaystyle \subseteq }$EXPTIME ${\displaystyle \subseteq }$ NEXPTIME ${\displaystyle \subseteq }$ EXPSPACE ${\displaystyle \subseteq }$ 2-EXPTIME ${\displaystyle \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 ${\displaystyle \subseteq }$ 2-EXPTIME, dal momento che una macchina di Turing alternante è potente almeno quanto una macchina deterministica di Turing.[1]

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 ${\displaystyle 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.[2]

Note

1. Christos Papadimitriou, Computational Complexity (1994), ISBN 978-0-201-53082-7. Sezione 20.1, corollario 3, pagina 495.
2. Jussi Rintanen, Complexity of Planning with Partial Observability (PDF), in Proceedings of International Conference on Automated Planning and Scheduling, AAAI Press, 2004, pp. 345–354.

Voci correlate

• Funzione esponenziale