En la teoría de la complejidad computacional , un problema computacional H se llama NP-difícil si, para cada problema L que puede resolverse en tiempo polinomial no determinista , hay una reducción del tiempo polinomial de L a H. Es decir, suponiendo que una solución para H requiere 1 unidad de tiempo, la solución de H se puede utilizar para resolver L en tiempo polinomial. [1] [2] Como consecuencia, encontrar un algoritmo de tiempo polinomial para resolver un solo problema NP-difícil daría algoritmos de tiempo polinomial para todos los problemas en la clase de complejidad NP . Como se sospecha que P≠NP , es poco probable que exista tal algoritmo. [3] Se sospecha que no existen algoritmos de tiempo polinómico para problemas NP-difíciles, pero eso no se ha demostrado. [4] Un ejemplo simple de un problema NP-difícil es el problema de suma de subconjuntos .
Informalmente, si H es NP-difícil, entonces es al menos tan difícil de resolver como los problemas en NP . Sin embargo, la dirección opuesta no es cierta: algunos problemas son indecidibles y, por lo tanto, incluso más difíciles de resolver que todos los problemas en NP, pero probablemente no son NP-difíciles (a menos que P=NP). [5]
Un problema de decisión H es NP-difícil cuando para cada problema L en NP, hay una reducción de muchos uno en tiempo polinomial de L a H. [1] : 80
Otra definición es requerir que haya una reducción del tiempo polinomial de un problema NP -completo G a H. [1] : 91 Como cualquier problema L en NP se reduce en tiempo polinomial a G , L se reduce a su vez a H en tiempo polinomial por lo que esta nueva definición implica la anterior. No restringe la clase NP-hard a problemas de decisión, y también incluye problemas de búsqueda o problemas de optimización .
Si P ≠ NP, entonces los problemas NP-difíciles no podrían resolverse en tiempo polinomial.
Algunos problemas de optimización NP-hard pueden aproximarse en tiempo polinomial hasta algún ratio de aproximación constante (en particular, los de APX ) o incluso hasta cualquier ratio de aproximación (los de PTAS o FPTAS ). Hay muchas clases de aproximabilidad, cada una de las cuales permite una aproximación hasta un nivel diferente. [6]
Todos los problemas NP-completos también son NP-difíciles (ver Lista de problemas NP-completos ). Por ejemplo, el problema de optimización de encontrar la ruta cíclica de menor costo a través de todos los nodos de un gráfico ponderado (comúnmente conocido como el problema del viajante ) es NP-difícil. [7] El problema de la suma de subconjuntos es otro ejemplo: dado un conjunto de números enteros, ¿cualquier subconjunto no vacío de ellos suma cero? Ese es un problema de decisión y resulta ser NP-completo.
Hay problemas de decisión que son NP-difíciles pero no NP-completos, como el problema de detención . Ese es el problema que pregunta "dado un programa y su entrada, ¿se ejecutará para siempre?" Esa es una pregunta de sí / no y también lo es un problema de decisión. Es fácil demostrar que el problema de detención es NP-difícil pero no NP-completo. Por ejemplo, el problema booleano de satisfacibilidad se puede reducir al problema de la detención transformándolo a la descripción de una máquina de Turing que intenta todas las asignaciones de valores de verdad y cuando encuentra uno que satisface la fórmula se detiene y, de lo contrario, entra en un bucle infinito. También es fácil ver que el problema de la detención no está en NP ya que todos los problemas en NP son decidibles en un número finito de operaciones, pero el problema de la detención, en general, es indecidible . También hay problemas NP-difíciles que no son NP-completos ni indecidibles . Por ejemplo, el lenguaje de las fórmulas booleanas cuantificadas verdaderas es decidible en el espacio polinomial , pero no en el tiempo polinomial no determinista (a menos que NP = PSPACE ). [8]
Los problemas NP-difíciles no tienen por qué ser elementos de la clase de complejidad NP. Como NP juega un papel central en la complejidad computacional , se utiliza como base de varias clases:
Los problemas NP-difíciles a menudo se abordan con lenguajes basados en reglas en áreas que incluyen: