Complejidad

NP-COMPLETITUD
A≤pol B si y sólo si (∀x)[x∈A⇔ f(x)∈B] y f polinómica
x∈A?

COMPLEJIDAD

NP-COMPLETITUD NP-

A
¿COMO PROBAR QUE EXISTE UN PROBLEMA NPCOMPLETO ?

f

SI NO B NP-completo

…Dos observaciones: 1. Un lenguaje L en NP es aceptado por una máquna de Turing no determinística ML de tiempo polinómico si y solo si el proceso de reconocimiento de cualquier string de L es unacomputación de tiempo polinómico. 2. Debe existir una función que traduzca cualquier instancia de L (ie, string de L) al alegado lenguaje completo
Intente alguna conclusión de 1 y 2, conclusió y no se pierda las próximas pró diapositivas!!!!!

B x∈B?

si y sólo si B∈NP y (∀A)[A∈NP: A≤pol B]

COMPLEJIDAD

NP-COMPLETITUD

• De 1. podemos concluir que se pueden identificar strings de L con lascorrespondientes computaciones de tiempo polinomial que hace ML para reconocerlos. • De 1 y 2, podemos concluir que tanto da que f transforme instancias de L en instancias del lenguaje candidato a completo en tiempo polinomial, como que transforme las correspondientes computaciones polinomiales del mismo modo…..
Siga la flecha y piense 3 minutos Casi estamos llegando a la conclusión, piense unminuto y conclusió trate de enunciarla…….. enunciarla……..

COMPLEJIDAD

NP-COMPLETITUD

• Aca sirve la noción de Lenguaje: “Un problema en NP” es exactamente un lenguaje aceptado por una máquina de Turing no determinística de tiempo polinómico. • …….. Y que ganamos con eso???
Siga la flecha y piense 2 minutos

• Digresión: Este modo de razonar, caracterizando lenguajes en términos decomputaciones no es nuevo en el campo de los lenguajes formales. El famoso Teorema de Nerode sigue una línea de pensamiento análogo…. Teorema (Myhill-Nerode): Un lenguaje es regular si y sólo si es la unión de algunas clases de equivalencia de una relación invariante a derecha y de índice finito.

COMPLEJIDAD

NP-COMPLETITUD

• En resumen, reuniendo las conclusiones que tenemos hasta ahora sepuede decir que:

• …ahora bien,cómo demostrar que “cualquier lenguaje en NP” se reduce a un misterioso y alegado candidato a ser completo?? ……..esto requiere algo de imaginación!!!
Imagine un par de minutos, y no se pierda las próximas diapositivas!!!!! pró

“si uno demuestra que cualquier computación computació de tiempo polinomial de cualquier máquina de má Turing no determinística –quereconoce algún determiní algú string- se puede traducir (reducir) en tiempo stringpolinomial a instancias del alegado –y aún ignoto- lenguaje (problema) en NP, entonces ignotoeste lenguaje será NP-completo”. será NP- completo”
Press down arrow ….

COMPLEJIDAD

NP-COMPLETITUD

COMPLEJIDAD
•

NP-COMPLETITUD

1. 2. 3.

satisfactibilidad de las fórmulas del cálculo proposicional.proposicional

La fórmula f M (x) contendrá las siguientes variables proposicionales. Las presentaremos dando su interpretación relativa a una computación de M: Ek t es V si y sólo si M en el paso t se encuentra en el estado qk. Aquí, 1≤ t≤T y 1≤ k≤ e. Sict es V si y sólo si el casillero c de la cinta de M contiene el símbolo a i en el paso t (1≤ i≤ s, c≥1, 1≤ t ≤T). Pct es V si y sólo si la cabeza de M seencuentra "observando" el casillero c en el paso t (1≤ c≤ T, 1≤ t≤ T).

Tenemos O(p2(n)) variables proposicionales. Debe notarse que en un máximo de T pasos M no puede mover la cabeza más que T casilleros a la derecha. En consecuencia, solo los casilleros c≤ T pueden ser relevantes en una computación de M.

COMPLEJIDAD

NP-COMPLETITUD

t
1≤t ≤T

• Proposición. El problema de lasatisfactibilidad de las fórmulas del cálculo proposicional (SAT) está en NP. (SAT ∈ NP).

Prueba. Ejercicio en clase (pensar 3’ 30’’)

Nótese que At afirma que la cabeza de la cinta se encuentra sobre un y sólo un casillero en el paso t. só Entonces, A afirma que esto ocurre en todos los pasos

COMPLEJIDAD

NP-COMPLETITUD
c ≥ 1, t ≤ T

• Teorema (Cook). El problema de determinar si una...