NEXPTIME

En teoría de la complejidad computacional, la clase de complejidad NEXPTIME es el conjunto de los problemas de decisión que pueden ser resueltos en una máquina de Turing no-determinista en tiempo O(2^p(n)), donde p(n) es una función polinomial sobre n.

En función de NTIME,

$\mbox{NEXPTIME} = \bigcup_{k\in\mathbb{N}} \mbox{NTIME}(2^{n^k})$