Editing NE (complexity)

In [[computational complexity theory]], the [[complexity class]] '''NE''' is the set of [[decision problem]]s that can be solved by a [[non-deterministic Turing machine]] in time [[Big O notation|O]](''k''<sup>n</sup>) for some ''k''.<ref>{{ComplexityZoo|NE|N#ne}}</ref>

'''NE''', unlike the similar class [[NEXPTIME]], is not closed under [[Polynomial-time reduction|polynomial-time]] [[many-one reduction]]s.

==Relationship to other classes==
{{Multiple issues|section=yes|
{{Unreferenced section|date=February 2023}}
{{Expand section|date=February 2023}}
}}

NE is contained by [[NEXPTIME]].

==See also==
* [[E (complexity)]]

==References==

<references/>

{{comp-sci-theory-stub}}

{{DEFAULTSORT:Ne (Complexity)}}
[[Category:Complexity classes]]