Nondeterministic exponential time

The class of decision problems decided by a nondeterministic Turing machine in time $2^{\mathrm{poly}(n)}$; equivalently, the languages whose membership has witnesses of exponential length that can be verified in exponential time.

See the complexity zoo entry here.

Notable problems

• Succinct versions of standard $\mathbf{NP}$-complete problems, such as Succinct 3SAT, in which the input is a circuit describing an exponentially large formula or graph, are $\mathbf{NEXP}$-complete — PY86.

Known relationships

• $\mathbf{EXP}\subseteq \mathbf{NEXP}$, and $\mathbf{NP}⊊\mathbf{NEXP}$ by the nondeterministic time hierarchy theorem — standard.
• $\mathbf{NEXP}$ is exactly the class of languages with multi-prover interactive proofs: MIP = NEXP — BFL90, FRS88.

Participates in

Produces Nondeterministic exponential time

• EXP ⊆ NEXP
• MIP = NEXP