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.
~1 min read
Article
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).
Connections
International Standard Book Number
Entity
Turing machine
Entity
OCLC, Inc.
Entity
quicksort
Entity
if and only if
Entity
computational complexity theory
Entity
NP
Entity
time complexity
Entity
decision problem
Entity
complexity class
Entity
Mathematical Reviews
Entity
oracle machine
Entity
polynomial hierarchy
Entity
David S. Johnson
Entity
polynomial-time reduction
Entity
Turing reduction
Entity
function problem
Entity
Michael Garey
Entity