NP-Completitud y Reducciones
Un problema NP-completo es uno de los más difíciles en la clase NP, en el sentido de que cada problema NP se reduce a él eficientemente, de modo que resolver rápidamente cualquier problema NP-completo resolvería todos ellos.
Definition
Un problema es NP-completo si pertenece a NP y cada problema en NP se reduce a él mediante una reducción en tiempo polinómico; tales problemas son los miembros máximamente difíciles de NP, equivalentes entre sí hasta una transformación eficiente.
Scope
Este tema abarca la clase NP de problemas verificables en tiempo polinómico, las reducciones muchos-a-uno en tiempo polinómico, el teorema de Cook-Levin que establece la satisfacibilidad como NP-completa, el catálogo de Karp de problemas combinatorios NP-completos, y la metodología para probar que nuevos problemas son NP-completos mediante reducción a partir de problemas conocidos.
Core questions
- ¿Qué significa que un problema sea de los más difíciles en NP?
- ¿Cómo identifica el teorema de Cook-Levin un primer problema NP-completo?
- ¿Cómo se utilizan las reducciones para probar que un nuevo problema es NP-completo?
- ¿Por qué la NP-completitud de un problema tiene implicaciones para miles de otros?
Key theories
- Teorema de Cook-Levin
- La satisfacibilidad booleana es NP-completa porque el cálculo de cualquier verificador en tiempo polinómico puede codificarse como una instancia de satisfacibilidad, proporcionando el problema completo fundamental del que se derivan otros.
- Reducciones de Karp y la red de problemas NP-completos
- Karp demostró que veintiún problemas naturales, desde la coloración de grafos hasta el problema de decisión del viajante, son NP-completos mediante reducciones en tiempo polinómico, iniciando la práctica de establecer la dificultad a través de una creciente red de reducciones.
Clinical relevance
La NP-completitud es el diagnóstico práctico de la intratabilidad: una vez que un problema de programación, logística, diseño o verificación se demuestra NP-completo, los ingenieros dejan de buscar un algoritmo exacto garantizado y rápido y recurren a algoritmos de aproximación, heurísticas, solucionadores de programación entera o restricciones que hacen que el problema sea tratable.
History
Cook demostró que la satisfacibilidad es NP-completa en 1971, y Levin obtuvo resultados equivalentes de forma independiente en la Unión Soviética. En 1972, Karp demostró veintiún problemas NP-completos adicionales, revelando la omnipresencia del fenómeno y convirtiendo la NP-completitud en la herramienta central para diagnosticar la dificultad computacional.
Key figures
- Stephen Cook
- Leonid Levin
- Richard Karp
Related topics
Seminal works
- cook1971
- karp1972
Frequently asked questions
- ¿Qué significa NP?
- NP significa tiempo polinómico no determinista. De manera equivalente, un problema está en NP si una solución propuesta puede verificarse en tiempo polinómico, incluso si encontrarla parece difícil. La ruta del viajante por debajo de una longitud dada es fácil de verificar una vez que se proporciona, pero aparentemente difícil de descubrir.
- ¿Cómo se prueba que un nuevo problema es NP-completo?
- Se demuestran dos cosas: que el problema está en NP, de modo que las soluciones candidatas se pueden verificar rápidamente, y que algún problema NP-completo conocido se reduce a él en tiempo polinómico. La reducción transfiere la dificultad conocida, colocando el nuevo problema entre los más difíciles en NP.