NP-Completitud e Intratabilidad

La NP-completitud identifica los problemas más difíciles en la clase NP —aquellos a los que se reduce cada problema NP— y proporciona el marco estándar para reconocer problemas para los cuales no se conoce o es poco probable un algoritmo eficiente.

Definition

Un problema de decisión es NP-completo si pertenece a NP (sus instancias afirmativas tienen certificados verificables eficientemente) y cada problema en NP se reduce a él en tiempo polinomial; tales problemas son los más difíciles en NP, y un algoritmo en tiempo polinomial para cualquiera de ellos produciría uno para todos.

Scope

Este tema cubre las clases de complejidad P y NP, las reducciones en tiempo polinomial, las definiciones de NP-dureza y NP-completitud, el teorema de Cook-Levin que establece la satisfacibilidad como NP-completa, el catálogo de problemas NP-completos de Karp y las consecuencias prácticas de la intratabilidad para el diseño de algoritmos. Aplica estos conceptos al reconocimiento y manejo de problemas difíciles; la teoría formal más amplia de las clases de complejidad computacional se trata en el subcampo de la teoría de la computación.

Core questions

• ¿Qué distingue las clases de complejidad P y NP?
• ¿Cómo transfiere una reducción en tiempo polinomial la dureza de un problema a otro?
• ¿Qué establece el teorema de Cook-Levin y por qué es central la satisfacibilidad?
• ¿Cómo se demuestra que un nuevo problema es NP-completo mediante la reducción de uno conocido?
• Una vez que un problema se demuestra NP-difícil, ¿qué estrategias algorítmicas quedan?

Key concepts

• clase de complejidad P
• clase de complejidad NP
• reducción en tiempo polinomial
• NP-dureza
• NP-completitud
• teorema de Cook-Levin
• satisfacibilidad booleana (SAT)
• pregunta P versus NP

Key theories

Teorema de Cook-Levin

El teorema de Cook-Levin demuestra que la satisfacibilidad booleana (SAT) es NP-completa: cada problema en NP se reduce a ella en tiempo polinomial, proporcionando el primer problema NP-completo y el ancla para demostrar la dificultad de otros.

Reducibilidad entre problemas combinatorios

Karp demostró que las reducciones en tiempo polinomial vinculan muchos problemas naturales —clique, cobertura de vértices, ciclo hamiltoniano, partición y otros— en una red de problemas NP-completos, de modo que cada uno puede demostrarse difícil mediante la reducción de otro.

Clinical relevance

Reconocer que un problema es NP-completo es uno de los resultados más útiles en la computación: indica a los ingenieros que no deben esperar un algoritmo exacto rápido y que, en su lugar, deben implementar algoritmos de aproximación, heurísticas, solucionadores exactos ajustados para instancias típicas o restricciones a casos especiales tratables. Muchos problemas de programación, enrutamiento, empaquetamiento y diseño son NP-completos.

History

Stephen Cook introdujo la NP-completitud en 1971, demostrando que SAT es NP-completo; Leonid Levin obtuvo resultados similares de forma independiente. El artículo de Richard Karp de 1972 mostró 21 problemas naturales NP-completos, estableciendo el alcance del marco. El libro de Garey y Johnson de 1979 catalogó cientos de problemas NP-completos y se convirtió en la referencia estándar.

Debates

P versus NP

Si P es igual a NP —si cada problema eficientemente verificable es también eficientemente resoluble— es el problema abierto más importante en el campo; casi todos los investigadores conjeturan que P no es igual a NP, pero la pregunta no está resuelta y es un problema del Premio del Milenio.

Key figures

• Stephen Cook
• Richard Karp
• Leonid Levin
• Michael Garey
• David Johnson

Seminal works

• cook1971
• karp1972
• cormen2009

Frequently asked questions

¿Cuál es la diferencia entre NP-difícil y NP-completo?

Un problema es NP-difícil si cada problema NP se reduce a él en tiempo polinomial, pero no necesita estar en NP ni ser un problema de decisión. Un problema es NP-completo si es NP-difícil y está en NP. Los problemas NP-completos son los problemas más difíciles que aún están en NP.

¿Significa la NP-completitud que un problema nunca puede resolverse?

No. Significa que no se conoce un algoritmo en tiempo polinomial para todas las entradas y es probable que no exista ninguno si P no es igual a NP. En la práctica, estos problemas se abordan con algoritmos de aproximación, heurísticas, solucionadores de tiempo exponencial que funcionan en instancias realistas o restringiéndose a casos especiales.