NE (complexity)

From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by imported>Siddharthist at 23:16, 28 February 2023 (Remove period from "See also" link). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.
(diff) ← Previous revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

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

Script error: No such module "Unsubst".

NE is contained by NEXPTIME.

See also

References

  1. ↑ Template:ComplexityZoo

Template:Comp-sci-theory-stub

Retrieved from "http://debianws.lexgopc.com/wiki143/index.php?title=NE_(complexity)&oldid=397425"