What is "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.

In terms of NTIME,

NEXPTIME = ⋃NTIME(2)

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 on input
• For all x in L, there exists a string y of length 2 such that
• For all x not in L and all strings y of length 2,

We know

and also, by the time hierarchy theorem, that

If , then ( padding argument); more precisely, if and only if there exist sparse languages in NP that are not in P.