## 3.4 PRUEBAS DE COMPLETITUD NP

La clase de complejidad NP-completo es el subconjunto de los problemas de decisión en NP tal que todo problema en NP se puede reducir en cada uno de los problemas de NP-completos. Se puede decir que los problemas de NP-completos son los problemas más difíciles de NP y muy probablemente no formen parte de la clase de complejidad P. La razón es que de tenerse una solución polinómica para un problema NP-completo, todos los problemas de NP tendrían también una solución en tiempo polinómico.

Si se pudiera demostrar que un problema NP-completo, llamémoslo A, no se pudiese resolver en tiempo polinómico, el resto de los problemas NP-completos tampoco se podrían resolver en tiempo polinómico. Esto se debe a que si uno de los problemas NP-completos distintos de A, digamos X, se pudiese resolver en tiempo polinómico, entonces A se podría resolver en tiempo polinómico, por definición de NP-completo. Ahora, pueden existir problemas en NP y que no sean NP-completos para los cuales exista solución polinómica, aun no existiendo solución para A.

- Se aplica a problemas de decisión, o sea problemas que tienen como respuesta SI o NO (aunque es sencillo ver que sus implicancias pueden extenderse a problemas de optimización).
- En el caso del problema del ajente viajero (Travelling Salesman Problem,TSP), la variante de decisión se podría formular como: “¿existe un circuito Hamiltoniano de longitud menor o igual a k?”
- Un problema de decisión π consiste entonces de un conjunto Dπ de instancias y un subconjunto Yπ ⊆ Dπ de instancias cuya respuesta es SI.

Método Clásico

Mostrar que el problema de interés sea NP-completo, porque este implicaría que el problema es entre los menos probables de pertenecer en la clase. Si algún problema NP-completo perteneciera a NP, aplicaría NP = P.

Si se sube a un nivel suficientemente general, muchos problemas resultan NP-completos. En muchos casos es importante identificar qué requisitos causan que el problema resulte NP-completo versus polinomial. Una técnica básica es estudiar el conjunto de instancias producidas por una reducción utilizada en la demostración de ser NP-completo para capturar otro problema NP-completo.

¿Cómo se prueba que un problema es NP-Completo?

El problema SAT consiste en decidir si, dada una fórmula lógica π expresada como conjunción de disyunciones (ej: π = x1 ∧ (x2 ∨ ¬x1) ∧ (x3 ∨ ¬x4 ∨ x1)), existe una valuación de sus variables que haga verdadera π.

Teorema de Cook (1971): SAT es NP-Completo

La demostración de Cook es directa: considera un problema gen érico π ∈ NP y una instancia genérica d ∈ Dπ. A partir de la hipotética NDTM que resuelve π, genera en tiempo polinomial una fórmula lógica π,d en forma normal (conjunción de disyunciones) tal que d ∈ Yπ si y sólo si π, d se satisface.

###