NP-easy
Sign in to saveAlso known as FP^NP
In complexity theory, the complexity class NP-easy is the set of function problems that are solvable in polynomial time by a deterministic Turing machine with an oracle for some decision problem in NP.
In the Vinony graph
Within Vinony's link graph, NP-easy is referenced by 3 other articles, and connects out to International Standard Book Number, Turing machine and OCLC, Inc..
It is catalogued under the topic Complexity classes.
Its subject is documented across 5 Wikipedia language editions.
~1 min read
Encyclopedic overview
2 sectionsContents
- Notes
- References
In complexity theory, the complexity class NP-easy is the set of function problems that are solvable in polynomial time by a deterministic Turing machine with an oracle for some decision problem in NP.
In other words, a problem X is NP-easy if and only if there exists some problem Y in NP such that X is polynomial-time Turing reducible to Y. This means that given an oracle for Y, there exists an algorithm that solves X in polynomial time (possibly by repeatedly using that oracle).
Excerpted from Wikipedia’s “NP-easy” article, available under the CC BY-SA 4.0 licence.