Tratabilidad y NP-Completitud
Clases de problemas
Muchos problemas se resuelven con
algoritmos polinómicos (O(nk)): problemas
tratables
 Hay problemas que no se pueden
resolver: problema de la parada.
 Hay problemas que no se pueden
resolver en tiempo polinónico ((nk)):
problemas intratables

Curso 2004-05
Antonio Fernández, GSyC
2
Problema de la parada

No existe ningún algoritmo que diga si un
programa va a parar en tiempo finito con una
entrada dada:



Supongamos que hay una función H(P,I) que lo
resuelve.
Construimos D(P):
If H(P,P) then loop forever
else stop
¿Qué debe hacer D(D)?
Curso 2004-05
Antonio Fernández, GSyC
3
Problemas NP-completos



Hay una clase de problemas que no se sabe si
son tratables: problemas NP-completos
Nadie ha encontrado algoritmos polinómicos
para ninguno de ellos.
Algunos muy parecidos a problemas tratables:


Ciclos eulerianos y hamiltonianos.
Satisfabilidad de 2-FNC y 3-FNC
Curso 2004-05
Antonio Fernández, GSyC
4
Clases P, NP y NPC
La clase P contiene todos los problemas
tratables.
 La clase NP contiene todos los problemas
que se pueden “verificar” en tiempo
polinómico. Claramente PNP.
 La clase NPC contiene todos los
problemas NP-completos

Curso 2004-05
Antonio Fernández, GSyC
5
Definicion NPC

Un problema es NP-Completo si:
1.
2.

Pertenece a NP.
Es tan “duro” como cualquier otro problema
en NP (es NP-duro).
Un problema es NP-duro si el que haya
un algoritmo polimómico para él implica
que lo hay para todos los problemas en
NP.
Curso 2004-05
Antonio Fernández, GSyC
6
P=NP?
Observa que si hubiera un algoritmo
polinómico para cualquier problema en
NPC entonces P=NP.
 La hipótesis más aceptada es que P≠NP.
 En general, si os encontráis un problema
NPC mejor buscáis alternativas
(simplificaciones, aproximaciones, etc.).

Curso 2004-05
Antonio Fernández, GSyC
7
Demostraciones de NPC
Se suelen usar problemas de decisión,
cuya respuesta en SI o NO.
 Se demuestra que el problema están en
NP.
 Se “reduce” un problema que se sabe
está en NPC a este problema.

Curso 2004-05
Antonio Fernández, GSyC
8
Reducción polinómica
Demuestra que un problema en NP-duro.
 Se parte de un problema p conocido en
NPC.
 Se construye un algoritmo polinómico que
transforma p en nuestro problema.
 Se concluye que si podemos resolver el
nuestro en tiempo polinómico, p se
resuelve en tiempo polinómico.

Curso 2004-05
Antonio Fernández, GSyC
9
Consejo



Si te encuentras con un problema que no eres
capaz de resolver de manera eficiente,
sospecha que puede ser NP-duro.
Intenta demostrar que lo es.
Si lo es, busca alternativas, porque mucha
gente inteligente ha intentado diseñar
algoritmos eficientes y no lo ha logrado.
Curso 2004-05
Antonio Fernández, GSyC
10
Descargar

Tratabilidad y NP