NP-fácil

En teoría de la complejidad , la clase de complejidad NP-fácil es el conjunto de problemas de función que pueden resolverse en tiempo polinomial por 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 reducible a Y mediante una función de Turing en tiempo polinomial. ^{[ 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 (ver el artículo sobre el problema de la función ) o para FΔ ₂ P (ver el artículo sobre la jerarquía de polinomios ).

Un ejemplo de problema NP-fácil es el de ordenar una lista de cadenas. El problema de decisión "¿es la cadena A mayor que la cadena B?" pertenece a NP. Existen algoritmos como Quicksort que pueden ordenar la lista utilizando 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 ordenación es NP-fácil.

También existen problemas más difíciles que son NP-fáciles. Véase NP-equivalente para un ejemplo.

La definición de NP-fácil utiliza una reducción de Turing en lugar de una reducción de muchos a uno porque las respuestas al problema Y son solo VERDADERO o FALSO, 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.

• Garey, Michael R.; Johnson , David S. (1979). Computadoras e intratabilidad: una guía a la teoría de la NP-completitud . Serie de libros en ciencias matemáticas (1.ª  ed.). Nueva York: WH Freeman and Company . ISBN 9780716710455. MR 0519066 . OCLC 247570676 .  .