Many-one reduction
In complexity theory, NP-easy is a set of problems similar to NP, except that NP-easy problems do not have to be decision problems.
A problem X is in NP-easy if and only if there exists some problem Y in NP such that X is Turing reducible to Y. This means that given a black box that solves instances of Y in unit time, there exists an algorithm that solves X in polynomial time by repeatedly using that black box.
An example of an NP-easy 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 NP-easy.
There are also more difficult problems that are NP-easy. See NP-equivalent for an example.
The definition of NP-easy used a Turing reduction rather than a many-one 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. NP-hard also uses a Turing reduction, for the same reason.
|
