NE (complexity)

Content sourced from Wikipedia, licensed under CC BY-SA 3.0.

NE stands for nondeterministic exponential time. It is the set of decision problems solvable by a nondeterministic Turing machine in time 2^{O(n)} (exponential in the input length). NE is contained in NEXPTIME (nondeterministic exponential time with time bound 2^{poly(n)}). Unlike some other classes, NE is not closed under polynomial-time many-one reductions.