What does NEXP mean in Computing?

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 2 n O ( 1 ) {\displaystyle 2^{n^{O(1)}}} . In terms of NTIME, N E X P T I M E = ⋃ k ∈ N N T I M E ( 2 n k ) {\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 2 p ( | x | ) {\displaystyle 2^{p(|x|)}} on input ( x , y ) {\displaystyle (x,y)} For all x in L, there exists a string y of length 2 q ( | x | ) {\displaystyle 2^{q(|x|)}} such that M ( x , y ) = 1 {\displaystyle M(x,y)=1} For all x not in L and all strings y of length 2 q ( | x | ) {\displaystyle 2^{q(|x|)}} , M ( x , y ) = 0 {\displaystyle M(x,y)=0} We know P ⊆ NP ⊆ EXPTIME ⊆ NEXPTIMEand also, by the time hierarchy theorem, that NP ⊊ NEXPTIMEIf 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.

see more »