## 3.4.1 PROBLEMAS NP COMPLETOS

La clase NP contiene numerosos problemas de importancia práctica.

Típicamente el problema tiene que ver con la construcción o existencia de un objeto matemático que satisface ciertas especificaciones. La versión de la construcción misma es un problema de optimización, donde la mejor construcción posible es la solución deseada. En la versión de decisión, que es la versión que pertenece a la clase NP, la pregunta es si existe por lo menos una configuración que cumpla con los requisitos del problema.

Un problema de decisión π es NP-completo si:

1. π ∈ NP 2. ∀π 0∈ NP, π 0≤p π Si un problema π verifica la condición.
2. π es NP-difícil (es al menos tan “difícil” como todos los problemas de NP).

Lista de 21 problemas NP-completos de Karp

Por Lista de 21 problemas NP-completos de Karp se entiende a una lista de 21 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. Esta lista fue elaborada en 1972 por el informático teórico Richard Karp, en su trabajo seminal "Reducibility Among Combinatorial Problems" (Reducibilidad entre Problemas Combinatorios), 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.

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

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

###