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(22p(n)), dove p(n) è una funzione polinomiale di n.

In termini di DTIME,

2-EXPTIME = ⋃ k ∈ N  DTIME  ( 2 2 n k ) . {\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 2 2 2 n k {\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
  Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica