NEXPTIME

In der Komplexitätstheorie steht NEXPTIME (manchmal auch nur NEXP) für die Komplexitätsklasse der Entscheidungsprobleme, die von einer nichtdeterministischen Turingmaschine in durch ${\displaystyle {\mathcal {O}}(2^{p(n)})}$ (siehe Landau-Notation) beschränkter Zeit akzeptiert werden können. Hierbei ist ${\displaystyle p(n)}$ ein beliebiges Polynom von der Eingabelänge ${\displaystyle n}$. In der DTIME-Notation ausgedrückt gilt also:

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