In computational complexity theory, the complexity class NE is the set of decision problems that can be solved by a non-deterministic Turing machine in time <math>2^{O(n)}
</math>. It is similar to NEXPTIME, the set of decision problems that can be solved by a non-deterministic Turing machine in time <math>2^{n^O(1)}
</math>. By definition, it is contained in NEXPTIME.
NE, unlike NEXPTIME, is not closed under polynomial-time many-one reductions.
See also
- E (complexity)