NEXPTIME

In computational complexity theory, the complexity class NEXPTIME (sometimes called NEXP) is the set of decision problems that can be solved by a non-deterministic Turing machine using time ${\displaystyle 2^{n^{O(1)}}}$.

In terms of NTIME,

${\displaystyle {\mathsf {NEXPTIME}}=\bigcup _{k\in \mathbb {N} }{\mathsf {NTIME}}(2^{n^{k}})}$

Alternatively, NEXPTIME can be defined using deterministic Turing machines as verifiers. A language L is in NEXPTIME if and only if there exist polynomials p and q, and a deterministic Turing machine M, such that

• For all x and y, the machine M runs in time ${\displaystyle 2^{p(|x|)}}$ on input ⁠${\displaystyle (x,y)}$⁠
• For all x in L, there exists a string y of length ${\displaystyle 2^{q(|x|)}}$ such that ⁠${\displaystyle M(x,y)=1}$⁠
• For all x not in L and all strings y of length ${\displaystyle 2^{q(|x|)}}$, ⁠${\displaystyle M(x,y)=0}$⁠

We know

P ⊆ NP ⊆ EXPTIME ⊆ NEXPTIME

and also, by the time hierarchy theorem, that

NP ⊊ NEXPTIME

If P = NP, then NEXPTIME = EXPTIME (padding argument); more precisely, E ≠ NE if and only if there exist sparse languages in NP that are not in P.^[1]