NEXPTIME

Nella teoria della complessità computazionale, la classe di complessità NEXPTIME (a volte detta NEXP) è l'insieme dei problemi decisionali risolvibili da una macchina di Turing non deterministica in tempo ${\displaystyle O(2^{p(n)})}$, dove ${\displaystyle p(n)}$ è una funzione polinomiale.

In termini di NTIME, ${\textstyle {\mathsf {NEXPTIME}}=\bigcup _{k\in \mathbb {N} }{\mathsf {NTIME}}(2^{n^{k}})}$.

Sappiamo che ${\displaystyle {\mathsf {P}}\subseteq {\mathsf {NP}}\subseteq {\mathsf {EXPTIME}}\subseteq {\mathsf {NEXPTIME}}}$ e, per il teorema della gerarchia temporale, che ${\displaystyle {\mathsf {NP}}\subsetneq {\mathsf {NEXPTIME}}}$.

Se P = NP, allora NEXPTIME = EXPTIME (ragionamento di padding); più precisamente, E ≠ NE se e solo se esistono linguaggi sparsi in NP che non sono in P.

NEXPTIME-completo

Un problema decisionale è NEXPTIME-completo se è in NEXPTIME, e ogni problema in NEXPTIME ha una riduzione in tempo polinomiale ad esso. In altre parole, se esiste un algoritmo in tempo polinomiale che trasforma le istanze di uno in istanze dell'altro con la stessa risposta. I problemi che sono NEXPTIME-completi potrebbero essere considerati i problemi più difficili in NEXPTIME. I problemi NEXPTIME-completi non sono in NP; è stato dimostrato che questi problemi non possono essere verificati in tempo polinomiale, dal teorema della gerarchia temporale.

Esempi di problemi NEXPTIME-completi

Problemi succinti

Un importante insieme di problemi NEXPTIME-completi riguarda i circuiti succinti. I circuiti succinti sono macchine semplici utilizzate per descrivere grafi in uno spazio esponenzialmente più piccolo. Accettano due indici di vertici come input e output, indipendentemente dalla presenza di un arco che li colleghi. Se risolvere un problema su un grafo in una rappresentazione naturale, come una matrice di adiacenza, è NP-completo, allora risolvere lo stesso problema su una rappresentazione circuitale succinta è NEXPTIME-completo, perché l'input è esponenzialmente più piccolo (sotto una condizione in cui la riduzione della NP-completezza è ottenuta tramite una "proiezione").^[1] Come semplice esempio, trovare un cammino hamiltoniano per un grafo così codificato è NEXPTIME-completo.

Logica

Il problema della soddisfacibilità di una formula in logica del primo ordine con due variabili è NEXPTIME-completo.^[2] Il problema di soddisfacibilità della logica del primo ordine con conteggio e con due variabili è NEXPTIME-completo.^[3]

Giochi

Decidere se una formula nelle formule booleana quantificate della dipendenza (DQBF, che è una versione con informazioni imperfette di QBF) è vera è NEXPTIME-completo.^[4]

Note

1. ^ C. Papadimitriou. Computational Complexity Addison-Wesley, 1994. ISBN 0-201-53082-1. Section 20.1, pg.492.
2. ^ (EN) Etessami, First-Order Logic with Two Variables and Unary Temporal Logic, in Information and Computation, vol. 179, 15 dicembre 2002, pp. 279–295, DOI:10.1006/inco.2001.2953, ISSN 0890-5401 (WC · ACNP).
3. ^ Ian Pratt-Hartmann, Proceedings of the Joint Meeting of the Twenty-Third EACSL Annual Conference on Computer Science Logic (CSL) and the Twenty-Ninth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), CSL-LICS '14, Association for Computing Machinery, 14 luglio 2014, pp. 1–10, DOI:10.1145/2603088.2603117, ISBN 978-1-4503-2886-9.
4. ^ Gary L. Peterson e John H. Reif, 20th Annual Symposium on Foundations of Computer Science (SFCS 1979), October 1979, pp. 348–363, DOI:10.1109/SFCS.1979.25.