En la teoría de la complejidad computacional , los 21 problemas NP-completos de Karp son un conjunto de problemas computacionales que son NP-completos . En su artículo de 1972, "Reducibilidad entre problemas combinatorios", [1] Richard Karp usó el teorema de Stephen Cook de 1971 de que el problema de satisfacibilidad booleano es NP-completo [2] (también llamado teorema de Cook-Levin ) para demostrar que hay una reducción de muchos-uno en el tiempo polinómico del problema de satisfacibilidad booleano a cada uno de los 21 combinatorios y gráficos teóricosproblemas computacionales, mostrando así que todos son NP-completos. Esta fue una de las primeras demostraciones de que muchos problemas computacionales naturales que ocurren en la ciencia de la computación son intratables desde el punto de vista computacional , y generó interés en el estudio de la completitud de NP y el problema P versus NP .
Los problemas
Los 21 problemas de Karp se muestran a continuación, muchos de ellos con sus nombres originales. El anidamiento indica la dirección de las reducciones utilizadas. Por ejemplo, Knapsack demostró ser NP-completo al reducir la cobertura Exact a Knapsack .
- Satisfabilidad : el problema de satisfacibilidad booleano para fórmulas en forma normal conjuntiva (a menudo denominada SAT)
- Programación de enteros 0-1 (una variación en la que solo se deben satisfacer las restricciones, sin optimización)
- Clique (ver también problema de conjuntos independientes )
- Establecer embalaje
- Cubierta de vértice
- Establecer cubierta
- Conjunto de nodos de comentarios
- Conjunto de arco de retroalimentación
- Circuito dirigido por Hamilton (el nombre de Karp, ahora generalmente llamado ciclo dirigido por Hamilton )
- Circuito de Hamilton no dirigido (el nombre de Karp, ahora generalmente llamado ciclo hamiltoniano no dirigido )
- Satisfacción con un máximo de 3 literales por cláusula (equivalente a 3-SAT)
- Número cromático (también llamado problema de coloración de gráficos )
- Portada de la camarilla
- Cobertura exacta
- Golpeando el set
- Árbol Steiner
- Coincidencia tridimensional
- Mochila (la definición de mochila de Karp está más cerca de la suma del subconjunto )
- Número cromático (también llamado problema de coloración de gráficos )
Con el paso del tiempo, se descubrió que muchos de los problemas pueden resolverse de manera eficiente si se restringen a casos especiales, o pueden resolverse dentro de cualquier porcentaje fijo del resultado óptimo. Sin embargo, David Zuckerman demostró en 1996 que cada uno de estos 21 problemas tiene una versión de optimización restringida que es imposible de aproximar dentro de cualquier factor constante a menos que P = NP, mostrando que el enfoque de Karp para la reducción se generaliza a un tipo específico de reducción por aproximación. [3] Sin embargo, tenga en cuenta que pueden ser diferentes de las versiones de optimización estándar de los problemas, que pueden tener algoritmos de aproximación (como en el caso del corte máximo).
Ver también
- Lista de problemas NP-completos
Notas
- ^ Karp 1972 .
- ^ Cocinero 1971 .
- ^ Zuckerman, 1996 .
Referencias
- Stephen Cook (1971). "La complejidad de los procedimientos de demostración de teoremas" . Proc. 3er Simposio Anual ACM sobre Teoría de la Computación (STOC) . págs. 151-158. doi : 10.1145 / 800157.805047 . S2CID 7573663 .
- Richard M. Karp (1972). "Reducibilidad entre problemas combinatorios" (PDF) . En RE Miller; JW Thatcher; JD Bohlinger (eds.). Complejidad de los cálculos informáticos . Nueva York: Pleno. págs. 85-103. doi : 10.1007 / 978-1-4684-2001-2_9 . ISBN 978-1-4684-2003-6.
- Zuckerman, David (1996). "Sobre versiones inapropiadas de problemas NP-Complete" . Revista SIAM de Computación . 25 (6): 1293-1304. doi : 10.1137 / S0097539794266407 . [1]