Tema
Reducciones y NP completitud
- Algoritmos
- Nivel avanzado
Un problema es NP completo cuando pertenece a NP y todo problema de NP se reduce a él en tiempo polinómico, de modo que resolverlo deprisa resolvería deprisa toda la clase.
Nombre en inglés
Reductions and NP completeness
Intuición
Una reducción de A a B es un traductor: Convierte cualquier instancia de A en una instancia de B de manera que las respuestas coincidan. El sentido importa y se confunde a menudo, porque para demostrar que B es difícil hay que reducir hacia B un problema ya conocido como difícil, nunca al revés. Así crece un catálogo que arranca en el problema de satisfacibilidad.
Fórmula
A <= B significa que existe f polinomica con x en A si y solo si f(x) en B ; P dentro de NP ; si B esta en P y A <= B entonces A esta en P
Ejemplo resuelto
Para demostrar que el problema del conjunto independiente es NP completo se reduce desde el problema de la camarilla: Dado un grafo G y un número k, se construye el grafo complementario y se pregunta por un conjunto independiente de tamaño k. Una camarilla de G es exactamente un conjunto independiente del complementario, y construir el complementario cuesta tiempo cuadrático, que es polinómico.
Errores frecuentes
- Reducir en el sentido contrario: Reducir el problema nuevo a uno ya conocido como difícil no demuestra nada sobre su dificultad.
- Olvidar demostrar que el problema pertenece a NP: Hace falta un certificado comprobable en tiempo polinómico, y sin él solo se prueba la dureza.
- Confundir NP con no polinómico: NP significa comprobable en tiempo polinómico, y todo problema de P pertenece también a NP.
Ejercicio
Se sabe que el problema A es NP completo y se construye una reducción polinómica de A a B. ¿Qué se concluye sobre B?
Ver la solución
Toda instancia de A se traduce a una de B, de modo que un algoritmo rápido para B resolvería también A. Por tanto B es al menos tan difícil como A, aunque para llamarlo NP completo falta comprobar que pertenece a NP.
Respuesta: que B es NP duro