En la teoría de la complejidad , la clase de complejidad NP-fácil es el conjunto de problemas de función que se pueden resolver en tiempo polinomial mediante una máquina de Turing determinista con un oráculo para algún problema de decisión en NP .
En otras palabras, un problema X es NP-fácil si y solo si existe algún problema Y en NP tal que X es Turing en tiempo polinómico reducible a Y. [1] Esto significa que dado un oráculo para Y, existe un algoritmo que resuelve X en tiempo polinomial (posiblemente usando repetidamente ese oráculo).
NP-easy es otro nombre para FP NP (consulte el artículo sobre problemas de función ) o para FΔ 2 P (consulte el artículo sobre jerarquía de polinomios ).
Un ejemplo de un problema NP-easy es el problema de ordenar una lista de cadenas. El problema de decisión "es la cadena A mayor que la cadena B" está en NP. Hay algoritmos como el ordenamiento rápido que pueden ordenar la lista usando solo un número polinomial de llamadas a la rutina de comparación, más una cantidad polinomial de trabajo adicional. Por lo tanto, la clasificación es NP-fácil.
También hay problemas más difíciles que son NP-easy. Consulte NP-equivalente para ver un ejemplo.
La definición de NP-easy usa una reducción de Turing en lugar de una reducción de muchos uno porque las respuestas al problema Y son solo VERDADERAS o FALSAS, pero las respuestas al problema X pueden ser más generales. Por lo tanto, no existe una forma general de traducir una instancia de X a una instancia de Y con la misma respuesta.
Notas
- ^ Garey y Johnson (1979) , p. 117, 120.
Referencias
- Garey, Michael R .; Johnson, David S. (1979), Computadoras e intratabilidad: una guía para la teoría de NP-Completeness , W. H. Freeman , ISBN 0-7167-1045-5.