stringtranslate.com

Dureza NP

Diagrama de Euler para conjuntos de problemas P, NP, NP-completos y NP-difíciles.
Diagrama de Euler para conjuntos de problemas P , NP , NP-completos y NP-difíciles. El lado izquierdo es válido bajo el supuesto de que P≠NP , mientras que el lado derecho es válido bajo el supuesto de que P=NP (excepto que el lenguaje vacío y su complemento nunca son NP-completos).

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]

Definición

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 .

Consecuencias

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]

Ejemplos

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]

Convención de nomenclatura NP

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.)

Áreas de aplicación

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

Véase también

Referencias

  1. ^ abc Leeuwen, Jan van , ed. (1998). Manual de informática teórica . Vol. A, Algoritmos y complejidad. Ámsterdam: Elsevier. ISBN 0262720140.OCLC 247934368  .
  2. ^ Knuth, Donald (1974). "Postdata sobre problemas NP-hard". ACM SIGACT News . 6 (2): 15–16. doi :10.1145/1008304.1008305. S2CID  46480926.
  3. ^ Daniel Pierre Bovet; Pierluigi Crescenzi (1994). Introducción a la Teoría de la Complejidad . Prentice Hall. pag. 69.ISBN 0-13-915380-2.
  4. ^ "Shtetl-Optimized » Blog Archive » The Scientific Case for P≠NP" (Archivo del blog de Shtetl-Optimized » El caso científico de P≠NP) www.scottaaronson.com . Consultado el 25 de septiembre de 2016 .
  5. ^ "¿Es indecidible(complemento de R) un subconjunto de NP-hard?". Stack Exchange en Ciencias de la Computación . Consultado el 9 de febrero de 2024 .
  6. ^ Escoffier, B.; Paschos, B.Th. (2010). "Un estudio sobre la estructura de las clases de aproximación". Computer Science Review . 4 (1): 19–40.
  7. ^ Lawler, EL ; Lenstra, JK ; Rinnooy Kan, AHG; Shmoys, DB (1985), El problema del viajante: una visita guiada a la optimización combinatoria , John Wiley & Sons, ISBN 0-471-90413-9.
  8. ^ Más precisamente, este lenguaje es PSPACE-completo ; véase, por ejemplo, Wegener, Ingo (2005), Complexity Theory: Exploring the Limits of Efficient Algorithms, Springer, p. 189, ISBN 9783540210450.