En la teoría de la complejidad computacional , un problema computacional H se denomina NP-duro si, para cada problema L que se puede resolver en tiempo polinomial no determinista , hay una reducción en tiempo polinomial de L a H. Es decir, suponiendo que una solución para H toma 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-duro daría algoritmos de tiempo polinomial para todos los problemas en la clase de complejidad NP . Como se sospecha, pero no se ha demostrado, que P≠NP , es poco probable que existan algoritmos de tiempo polinomial para problemas NP-duro. [3] [4]
Un ejemplo simple de un problema NP-duro es el problema de suma de subconjuntos .
De manera informal, si H es NP-hard, 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 es demostrable que no son NP-hard (a menos que P=NP). [5]
Un problema de decisión H es NP-duro cuando para cada problema L en NP, existe 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 en 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-hard no podrían resolverse en tiempo polinomial.
Algunos problemas de optimización NP-hard pueden aproximarse en tiempo polinomial hasta una cierta relación de aproximación constante (en particular, aquellos en APX ) o incluso hasta cualquier relación de aproximación (aquellos en PTAS o FPTAS ). Existen muchas clases de aproximabilidad, cada una de las cuales permite la aproximación hasta un nivel diferente. [6]
Todos los problemas NP-completos son también NP-difíciles (véase 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 grafo 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-hard pero no NP-completos, como el problema de la 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, por lo tanto, es un problema de decisión. Es fácil demostrar que el problema de la detención es NP-hard pero no NP-completo. Por ejemplo, el problema de satisfacibilidad booleano se puede reducir al problema de la detención transformándolo en la descripción de una máquina de Turing que prueba todas las asignaciones de valores de verdad y cuando encuentra una 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-hard que no son ni 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-hard no tienen por qué ser elementos de la clase de complejidad NP. Como NP desempeña un papel central en la complejidad computacional , se utiliza como base de varias clases:
Los problemas NP-hard suelen abordarse con lenguajes basados en reglas en áreas que incluyen: