Jump to content

NE (complexity)

From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by NatusRoma (talk | contribs) at 15:04, 21 May 2005 (math-stub). The present address (URL) is a permanent link to this revision, which may differ significantly from the current 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.

Stub icon

This mathematics-related article is a stub. You can help Wikipedia by expanding it.

Retrieved from "https://en.wikipedia.org/w/index.php?title=NE_(complexity)&oldid=16484044"