Veintiún problemas NP-completos de Karp

En teoría de complejidad computacional, los veintiún (21) problemas NP-completos de Karp son un conjunto de problemas computacionales famosos, que tratan sobre combinatoria y teoría de grafos y que cumplen la característica en común de que todos ellos pertenecen a la clase de complejidad de los NP-completos. La demostración fue elaborada en 1972 por el informático teórico Richard Karp, en su trabajo seminal "Reducibility Among Combinatorial Problems" (Reducibilidad entre Problemas Combinatorios),[1] como profundización del trabajo de Stephen Cook, quien en 1971 había demostrado uno de los resultados más importantes y pioneros de la complejidad computacional: la NP-completitud del problema de satisfacibilidad booleana.[2]

El descubrimiento de Karp de que todos estos importantes problemas eran NP-completos motivó el estudio de la NP-completitud y de la indagación en la famosa pregunta, de si P = NP.

Los problemas

Mientras que la pertenencia del problema SAT o de satisfacibilidad booleana a la clase de los NP-completos fue demostrada utilizando mecanismos particulares, las pertenencias de los 21 problemas siguientes fueron demostradas mediante reducciones polinomiales. Así, el problema SAT se redujo polinomialmente a los problemas 0-1 INTEGER PROGRAMMING, CLIQUE y 3-SAT, y estos a su vez se redujeron a otros varios. La lista completa es la que se muestra a continuación. Las sangrías denotan el hecho que la NP-completitud del problema fue demostrada por reducción polinomial del problema en el nivel directamente superior. Note que los nombres de los problemas están escritos con letras mayúsculas y corresponden a abreviaciones del nombre en inglés, como es lo usual; junto a ellos, entre paréntesis, se escribe la traducción del nombre en español.

Tras un tiempo se descubrió que muchos de estos problemas podían ser resueltos si su enunciado se particularizaba a unas ciertas clases, o podían ser resueltos aproximadamente con un error máximo de un cierto porcentaje. Sin embargo David Zuckerman demostró en 1996 que cada uno de estos 21 problemas tiene una versión restringida de optimización que es no aproximable a menos que P = NP, demostrando que la versión de la reducción, dada por Karp, generaliza un tipo específico de reducción por aproximación.[3]

Véase también

Referencias
  1. Richard M. Karp (1972). «Reducibility Among Combinatorial Problems». En R. E. Miller and J. W. Thatcher (editors), ed. Complexity of Computer Computations. New York: Plenum. pp. 85-103.
  2. Stephen Cook (1971). «The Complexity of Theorem Proving Procedures». Proceedings of the third annual ACM symposium on Theory of computing. pp. 151-158.
  3. David Zuckerman (1996). «On Unapproximable Versions of NP-Complete Problems». SIAM Journal on Computing 25 (6): 1293-1304.
Este artículo ha sido escrito por Wikipedia. El texto está disponible bajo la licencia Creative Commons - Atribución - CompartirIgual. Pueden aplicarse cláusulas adicionales a los archivos multimedia.