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 , dove è una funzione polinomiale.
In termini di NTIME, .
Sappiamo che e, per il teorema della gerarchia temporale, che .
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.
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.
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"). Come semplice esempio, trovare un cammino hamiltoniano per un grafo così codificato è NEXPTIME-completo.
Il problema della soddisfacibilità di una formula in logica del primo ordine con due variabili è NEXPTIME-completo. Il problema di soddisfacibilità della logica del primo ordine con conteggio e con due variabili è NEXPTIME-completo.
Decidere se una formula nelle formule booleana quantificate della dipendenza (DQBF, che è una versione con informazioni imperfette di QBF) è vera è NEXPTIME-completo.