NEXP
NEXP, the nondeterministic exponential time class, consists of all decision problems solvable by a nondeterministic Turing machine in time 2^{p(n)} for some polynomial p, where n is the input length. Equivalently, it is NTIME(2^{poly(n)}). It is the nondeterministic analogue of EXP, since deterministic exponential time is contained in the nondeterministic counterpart (EXP ⊆ NEXP).
The relationship with other complexity classes is a central topic in complexity theory. It is known that
NEXP-complete problems exist, serving as the hardest problems in the class under polynomial-time many-one reductions. A
NEXP plays a role in the study of nondeterminism at exponential scales and in examining time hierarchy