View source for NP-easy

In [[computational complexity theory|complexity theory]], the [[complexity class]] '''NP-easy''' is the set of [[function problem]]s that are solvable in [[polynomial time]]  by a [[deterministic Turing machine]] with an [[oracle machine|oracle]] for some [[decision problem]] in [[NP (complexity)|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 reduction|polynomial-time Turing reducible]] to Y.<ref>{{harvtxt|Garey|Johnson|1979}}, p. 117, 120.</ref>  This means that given an [[oracle machine|oracle]] for Y, there exists an algorithm that solves X in polynomial time (possibly by repeatedly using that oracle).

NP-easy is another name for FP<sup>NP</sup> (see the [[function problem]] article) or for FΔ<sub>2</sub>P (see the [[polynomial hierarchy]] article).

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 uses 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.  

==Notes==
{{reflist}}

==References==
* {{Garey-Johnson}}.

{{DEFAULTSORT:Np-Easy}}
[[Category:Complexity classes]]