## 3.3.3 COMPLETITUD NP

Recordando que la integridad de NP se trata de mostrar cuán difícil es un problema en lugar de cuán fácil es, usamos polinomios, reducciones de tiempo en la forma opuesta para mostrar que un problema es NP-completo.

Teoría de la NP-completitud

La Teoría de la NP-completitud no proporciona un método para obtener algoritmos de tiempo polinómico. Ni dice que estos algoritmos no existan. Lo que muestra es que muchos de los problemas para los cuales no conocemos algoritmos polinómicos están relacionados (computacionalmente).

Dos clases de problemas: NP-completos y NP-difíciles.

• Un problema NP-completo tiene la propiedad de que puede ser resuelto en tiempo polinómico si y solo si todos los problemas NP-completos pueden ser resueltos en tiempo polinómico.

• Si un problema NP-difícil puede ser resuelto en tiempo polinómico, entonces todos los problemas NP-completos pueden ser resueltos en tiempo polinómico.

Ejemplos

Problema del Viajante

Dado un grafo dirigido y valorado, el problema de optimización del viajante consiste en encontrar un circuito de costo mínimo que empiece en un vértice, acabe en ese vértice, y visite al resto de vértices exactamente una vez. El problema de decisión del viajante consiste en determinar, dado un positivo d, si el grafo tiene un circuito de costo no mayor que d. El problema de decisión correspondiente no es más difícil que el de optimización.

Problema del Cliqué

Un cliqué de un grafo no dirigido G = ( V, A) es un subconjunto W de V tal que cada vértice de W es adyacente al resto de vértices en W.

El problema de optimización del cliqué consiste en encontrar el tamaño de un cliqué maximal. El problema de decisión del cliqué consiste en determinar, dado un entero positivo k, si existe un cliqué que contenga al menos k vértices.

###