Teoría de la Completitud NP

Capítulo 2
Teoría de la
Completitud NP
Computers and Intractability,
A Guide to the Theory of NP-Completeness
Michael R. Garey / David S. Johnson

Dra. Laura Cruz Reyes

Panorama del Tema


El tema consta de dos partes:
 En

la primera parte se explica un procedimiento
teórico para clasificar un problema de optimización
en uno de dos tipos: P (informalmente, el tipo deproblemas "fáciles") y NPC (informalmente, el tipo de
problemas "difíciles"). Este procedimiento se basa en
el uso de máquinas de Turing.
 En la segunda parte se explica un procedimiento
práctico para determinar si un problema de
optimización pertenece a la clase NPC, para lo cual
se usan funciones de transformación.
Dra. Laura Cruz Reyes

PROCEDIMIENTO TEÓRICO PARA
CLASIFICAR PROBLEMASDra. Laura Cruz Reyes

Teoría de la Completitud NP






Aplica sólo a problemas de decisión.
Un problema de decisión tiene sólo dos posibles
soluciones: “sí” o “no”.
La solución se define en función de la
aceptación del lenguaje de ejemplares codificados, por una máquina de Turing (MT).
Como las máquinas de Turing sólo tienen la
capacidad de aceptar o no una cadena, los
únicosproblemas que pueden resolver son los
de decisión.
Dra. Laura Cruz Reyes

Planteamiento de un Problema
Problema: Factorización de un número

Factorización de n
n=100

Entrada o ejemplar genérico:
Sea n un número natural

n=192

Salida en términos del ejemplar genérico:
Una factorización de n

Ejemplares

Dra. Laura Cruz Reyes

Complejidad de Algoritmos y
ProblemasProblema 

Algoritmos
W1(n) = O(n)
Más eficiente

Peor caso

W2(n) = O(n2)
Wi(n) = O(n logn)

Ejemplares
de tamaño n

La complejidad de  es igual a la complejidad del
algoritmo más eficiente para el peor caso, es decir
min(W1(n), W2(n), ...)
Dra. Laura Cruz Reyes

Problema de Decisión (PD)


Un problema de decisión es un problema que
sólo tiene dos posibles respuestas: “sí” o“no”.



Problema del agente viajero
Ejemplar:
Un grafo G con pesos y un número real B.
Pregunta:
¿G contiene un ciclo hamiltoniano con longitud  B?

Dra. Laura Cruz Reyes

Definición Formal de un PD






Un problema de decisión  = (D, Y)
es una pareja formada por un
conjunto de ejemplares D y un
subconjunto de ejemplares-sí Y 
D.

Los ejemplares de D se obtienen apartir de una ejemplar genérico.
Un ejemplar i pertenece a Y, si y
sólo si la respuesta a la pregunta
del problema es sí para ese
ejemplar.
Dra. Laura Cruz Reyes



D

Y

Planteamiento de un PD


Ejemplar genérico:




Especificación del ejemplar genérico en términos de componentes formales: conjuntos,
grafos, funciones, números, etc.

Pregunta sí-no:


Preguntaformulada en términos del ejemplar
genérico, cuya respuesta puede ser sí o no.

Dra. Laura Cruz Reyes

Ejemplo de un PD
Problema del Agente Viajero
(TSP, Traveling Salesman Problem)


Ejemplar: Un grafo G con pesos d y un número real B.

C  {c1 , c2 , ..., cm }

d (ci , c j )  Z  para cada par de ciudades ci , c j  C

BZ


Pregunta: ¿G contiene un ciclo hamiltonianocon longitud  B?
m 1

¿

 d c   , c   
i 1

i

i 1

 d c m  , c 1   B ?

Dra. Laura Cruz Reyes

Ejemplo de un PD
Problema del Agente Viajero
(TSP, Traveling Salesman Problem)


Ejemplar: Un grafo G con pesos d y un número real B.

C  {c1 , c2 , c3 }

c1

d (c1 , c2 )  2; d (c2 , c3 )  67; d (c3 , c1 )  34

B  150

2

34

c2

67
c3

Pregunta: ¿G contiene un ciclo hamiltoniano con longitud  B?
m 1

¿

 d c   , c   
i 1

i

i 1

 d c m  , c 1   B ?

Dra. Laura Cruz Reyes

recorrido (ciclo hamiltoniano)
 = 1, 3, 2
34 + 67 + 2 ≤ 150

Decisión y Optimización


Un problema de decisión se puede derivar de uno de
optimización. En el caso de un problema de
minimización, se...