NE (complexity)

From Free net encyclopedia

Revision as of 15:04, 21 May 2005; view current revision
←Older revision | Newer revision→

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.

Image:E-to-the-i-pi.svg This mathematics-related article is a stub. You can help Wikipedia by expanding it.
Retrieved from "http://www.netipedia.com/index.php/NE_%28complexity%29"