Top Qs
Timeline
Chat
Perspective
NE (complexity)
From Wikipedia, the free encyclopedia
Remove ads
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.[1]
NE, unlike the similar class NEXPTIME, is not closed under polynomial-time many-one reductions.
Relationship to other classes
 | This section has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these messages)
|
![[icon]](#/media/File:Wiki_letter_w_cropped.svg){kind=small}
NE is contained by NEXPTIME.
See also
References
Wikiwand - on
Seamless Wikipedia browsing. On steroids.
Remove ads