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 template messages) This section does not cite any sources. Please help improve this section by adding citations to reliable sources. Unsourced material may be challenged and removed. (February 2023) (Learn how and when to remove this template message) This section needs expansion. You can help by adding to it. (February 2023) (Learn how and when to remove this template message)

NE is contained by NEXPTIME.

See also

References

  1. ^ Complexity Zoo: NE
Categories