NE (complexity)

In computational complexity theory, NE stands for "nondeterministic exponential time." This complexity class consists of decision problems for which a solution can be verified by a deterministic Turing machine in exponential time, given a suitable certificate (or witness) that satisfies the problem.