NE (complexity)

From Wikipedia, the free encyclopedia

You have new messages (last change).

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 O(kn) for some k.

NE is less important to complexity theory than the similar class NEXPTIME because it is not closed under polynomial-time many-one reductions.

 This mathematics-related article is a stub. You can help Wikipedia by expanding it.
Retrieved from "http://en.wikipedia.org../../../n/e/_/NE_%28complexity%29_7992.html"