In complexity theory, the complexity class NP-easy is the set of function problems that are solvable in polynomial time by a nondeterministic 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). NP-easy is another name for FPNP (see the function problem article) or for FΔ2P (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 pol
En la teoría de la complejidad, la clase de complejidad NP-easy es el conjunto de problemas de funciones que son solucionables en tiempo polinómico por una máquina de Turing no determinista con un oráculo para algún problema de decisión en NP. En otras palabras, un problema X es NP-easy si y sólo si existe algún problema Y en NP tal que X es polinómico-tiempo de Turing reducible a Y. Esto significa que dado un oráculo para Y, existe un algoritmo que resuelve X en tiempo polinómico (posiblemente mediante el uso repetido de ese oráculo). NP-easy es otro nombre para FPNP (véase el artículo del problema de la función) o para FΔ2P (véase el artículo de la jerarquía polinómica).