In complexity theory, the complexity class NPeasy 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 NPeasy if and only if there exists some problem Y in NP such that X is polynomialtime Turing reducible to Y.^{[1]} This means that given an oracle for Y, there exists an algorithm that solves X in polynomial time (possibly by repeatedly using that oracle).
NPeasy is another name for FP^{NP} (see the function problem article) or for FΔ_{2}P (see the polynomial hierarchy article).
An example of an NPeasy problem is the problem of sorting a list of strings. The decision problem "is string A greater than string B" is in NP. There are algorithms such as Quicksort that can sort the list using only a polynomial number of calls to the comparison routine, plus a polynomial amount of additional work. Therefore, sorting is NPeasy.
There are also more difficult problems that are NPeasy. See NPequivalent for an example.
The definition of NPeasy uses a Turing reduction rather than a manyone reduction because the answers to problem Y are only TRUE or FALSE, but the answers to problem X can be more general. Therefore, there is no general way to translate an instance of X to an instance of Y with the same answer.
Notes
References
Full article ▸
