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

NE is contained by NEXPTIME.

See also

References

Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.

Remove ads