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 EXP ⊆ NEXP, because nondeterminism can simulate deterministic computation. It is an open question whether NEXP ⊆ EXP; most researchers believe NEXP is strictly larger, but no proof currently establishes or refutes this containment. As with many high-level complexity classes, definitive separations or collapses remain unknown.

NEXP-complete problems exist, serving as the hardest problems in the class under polynomial-time many-one reductions. A canonical example is succinct SAT: given a Boolean circuit that encodes an exponentially large 3-CNF formula, decide whether that formula is satisfiable. The problem illustrates how succinct representations can amplify complexity, placing the task in NEXP rather than in NP or PSPACE. Other NEXP-complete problems arise from similar succinct or compressed representations of classical NP problems.

NEXP plays a role in the study of nondeterminism at exponential scales and in examining time hierarchy phenomena at higher complexity levels. It is often contrasted with EXP and related classes to map the landscape of computational power when time bounds are exponential.