Dureza NP

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 probablemente no sean 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:

notario público

Clase de problemas de decisión computacional para los cuales cualquier solución dada puede verificarse como una solución en tiempo polinomial mediante una máquina de Turing determinista (o puede resolverse mediante una máquina de Turing no determinista en tiempo polinomial).

NP-duro

Clase de problemas que son al menos tan difíciles como los problemas más difíciles en NP. Los problemas que son NP-difíciles no tienen por qué ser elementos de NP; de hecho, puede que ni siquiera sean decidibles.

NP-completo

Clase de problemas de decisión que contiene los problemas más difíciles en NP. Cada problema NP-completo debe estar en NP.

NP-fácil

A lo sumo tan duro como NP, pero no necesariamente en NP.

NP-equivalente

Problemas de decisión que son tanto NP-difíciles como NP-fáciles, pero no necesariamente NP.

NP-intermedio

Si P y NP son diferentes, entonces existen problemas de decisión en la región de NP que se encuentran entre P y los problemas NP-completos. (Si P y NP son de la misma clase, entonces no existen problemas NP-intermedios porque en este caso todo problema NP-completo caería en P, y por definición, todo problema en NP puede reducirse a un problema NP-completo.)

Los problemas NP-hard suelen abordarse con lenguajes basados ​​en reglas en áreas que incluyen:

• Cálculo aproximado
• Configuración
• Criptografía
• Minería de datos
• Apoyo a la toma de decisiones
• Filogenética
• Planificación
• Monitoreo y control de procesos
• Listas o horarios
• Enrutamiento/enrutamiento de vehículos
• Programación

• Listas de problemas
• Lista de problemas sin resolver
• Reducción (complejidad)
• Incognoscibilidad

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