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.

SAT (Problema de satisfacibilidad booleana, para fórmulas en forma normal conjuntiva)
- 0-1 INTEGER PROGRAMMING (Problema de la programación lineal entera)
- CLIQUE (Problema del clique, véase también Problema del conjunto independiente)
  - SET PACKING (Problema del empaquetamiento de conjuntos)
  - VERTEX COVER (Problema de la cobertura de vértices)
    - SET COVERING (Problema del conjunto de cobertura)
    - FEEDBACK NODE SET
    - FEEDBACK ARC SET
    - DIRECTED HAMILTONIAN CIRCUIT (Problema del circuito hamiltoniano dirigido)
      - UNDIRECTED HAMILTONIAN CIRCUIT (Problema del circuito hamiltoniano no dirigido)
- 3-SAT (Problema de satisfacibilidad booleana de 3 variables por cláusula)
  - CHROMATIC NUMBER (Problema de la coloración de grafos)
    - CLIQUE COVER (Problema de la cobertura de cliques)
    - EXACT COVER (Problema de la cobertura exacta)
      - HITTING SET
      - STEINER TREE
      - 3-DIMENSIONAL MATCHING (Problema del matching tridimensional)
      - KNAPSACK (Problema de la mochila)
        JOB SEQUENCING (Problema de las secuencias de trabajo)
        
        PARTITION (Problema de la partición)
        MAX-CUT (Problema del corte máximo)

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

↑ 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.
↑ Stephen Cook (1971). «The Complexity of Theorem Proving Procedures». Proceedings of the third annual ACM symposium on Theory of computing. pp. 151-158.
↑ David Zuckerman (1996). «On Unapproximable Versions of NP-Complete Problems». SIAM Journal on Computing 25 (6): 1293-1304.

Datos: Q1734364

[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.

[1]

[2]

[3]