De Wikipedia, la enciclopedia libre
  (Redirigido desde NP-hard )
Saltar a navegación Saltar a búsqueda
Para una introducción más suave, vea el problema P versus NP .
Diagrama de Euler para un conjunto de problemas P, NP, NP-completo y NP-difícil.
Diagrama de Euler para un conjunto de problemas P , NP , NP-completo y NP-difícil. 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 , la dureza NP ( dureza de tiempo polinomial no determinista ) es la propiedad definitoria de una clase de problemas que son informalmente "al menos tan difíciles como los problemas más difíciles de NP ". Un ejemplo simple de un problema NP-difícil es el problema de suma de subconjuntos .

Una especificación más precisa es: un problema H es NP-difícil cuando cada problema L en NP puede reducirse en tiempo polinómico a H ; es decir, suponiendo que una solución para H toma 1 unidad de tiempo, la solución de H se puede usar para resolver L en tiempo polinomial. [1] [2] Como consecuencia, encontrar un algoritmo de tiempo polinomial para resolver cualquier problema NP-difícil daría algoritmos de tiempo polinomial para todos los problemas en NP. Como se sospecha que P NP , es poco probable que exista tal algoritmo. [3]

Un error común es que el NP en "NP-hard" significa "no polinomial" cuando en realidad significa " problemas aceptables polinomiales no deterministas ". [4] Se sospecha que no existen algoritmos de tiempo polinómico para problemas NP-hard, pero eso no ha sido probado. [5] Además, la clase P , en la que todos los problemas se pueden resolver en tiempo polinómico, está incluida en la clase NP . [6]

Definición [ editar ]

Un problema de decisión H es NP-duro cuando para cada problema L en NP, hay un tiempo polinomio de reducción mucho-uno de L a H . [1] : 80 Una definición equivalente es exigir que cada problema L en NP puede ser resuelto en tiempo polinómico por una máquina oráculo con un oráculo para H . [7] De manera informal, se puede pensar en un algoritmo que llama a dicha máquina oráculo como una subrutina para resolver H y resuelve L en tiempo polinomial si la llamada a la subrutina toma solo un paso para calcular.

Otra definición es requerir que haya una reducción de tiempo polinómico de un NP-completo problema G a H . [1] : 91 Como cualquier problema L en NP 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. Curiosamente, 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 [ editar ]

Si P ≠ NP, entonces los problemas NP-difíciles no podrían resolverse en tiempo polinomial.

Algunos problemas de optimización NP-hard se pueden aproximar en tiempo polinómico hasta una proporción de aproximación constante (en particular, los de APX ) o incluso hasta cualquier proporción de aproximación (los de PTAS o FPTAS ).

Ejemplos [ editar ]

Un ejemplo de un problema NP-difícil es el problema de suma de subconjuntos de decisión : dado un conjunto de números enteros, ¿algún subconjunto no vacío de ellos suma cero? Ese es un problema de decisión y resulta ser NP-completo. Otro ejemplo de un problema NP-difícil es 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. Esto se conoce comúnmente como el problema del viajante . [8]

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, ¿funcionará 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-duro 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 todos los valores de verdad.asignaciones 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 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 ). [9]

Convención de nomenclatura NP [ editar ]

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:

notario público
Clase de problemas de decisión computacional para los cuales cualquier solución de sí dada puede ser verificada como una solución en tiempo polinomial por una máquina de Turing determinista (o solucionable por 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-hard no tienen por qué ser elementos de NP; de hecho, es posible 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 tiene que estar en NP.
NP-fácil
Como mucho tan duro como NP, pero no necesariamente en NP.
NP-equivalente
Problemas de decisión que son NP-hard y NP-easy, pero no necesariamente en 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 los problemas NP-intermedios no existen porque en este caso todos los problemas NP-completos caerían en P y, por definición, todos los problemas en NP pueden reducirse a un problema NP-completo. )

Áreas de aplicación [ editar ]

Los problemas NP-hard a menudo se abordan con lenguajes basados ​​en reglas en áreas que incluyen:

  • Computación aproximada
  • Configuración
  • Criptografía
  • Procesamiento de datos
  • Apoyo a las decisiones
  • Filogenética
  • Planificación
  • Monitoreo y control de procesos
  • Listas u horarios
  • Enrutamiento / enrutamiento de vehículos
  • Planificación

Referencias [ editar ]

  1. ↑ a b c Leeuwen, Jan van , ed. (1998). Manual de Informática Teórica . Vol. A. Algoritmos y complejidad. Amsterdam: Elsevier. ISBN 0262720140. OCLC  247934368 .
  2. ^ Knuth, Donald (1974). "Posdata sobre problemas NP-hard". Noticias ACM SIGACT . 6 (2): 15–16. doi : 10.1145 / 1008304.1008305 .
  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. ^ "P y NP" . www.cs.uky.edu . Archivado desde el original el 19 de septiembre de 2016 . Consultado el 25 de septiembre de 2016 .
  5. ^ "Shtetl-Optimized» Blog Archive »El caso científico de P ≠ NP" . www.scottaaronson.com . Consultado el 25 de septiembre de 2016 .
  6. ^ "Conferencia 6 de PHYS771: P, NP y amigos" . www.scottaaronson.com . Consultado el 25 de septiembre de 2016 .
  7. ^ VJ Rayward-Smith (1986). Un primer curso de computabilidad . Blackwell. pag. 159. ISBN 0-632-01307-9.
  8. ^ Lawler, EL ; Lenstra, JK ; Rinnooy Kan, AHG; Shmoys, DB (1985), El problema del vendedor ambulante: un recorrido guiado por la optimización combinatoria , John Wiley & Sons, ISBN 0-471-90413-9.
  9. ^ 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.
  • Michael R. Garey y David S. Johnson (1979). Computadoras e intratabilidad: una guía para la teoría de NP-Completeness . WH Freeman. ISBN 0-7167-1045-5.