NE (complexity)

In computational complexity theory, the complexity classNE 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-timemany-one reductions.

Relationship to other classes

NE is contained by NEXPTIME.

See also

References

  1. ^Complexity Zoo: NE
P ≟ NP 

This theoretical computer science–related article is a stub. You can help Wikipedia by adding missing information.

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