Puntos extra - Algoritmos Optimizacion

 La teoria de NP-completitud
Se aplica a problemas de decision, o sea problemas que tienen
como respuesta SI o NO (aunque es sencillo ver que sus
implicancias pueden extenderse a problemas de optimizacion).
En el caso del problema de TSP, la variante de decision se
podria formular como: “¿existe un circuito Hamiltoniano de
longitud menor o igual a k?”
Un problema de decision π consiste entonces de un conjunto
Dπ de instancias y un subc



Modelos de Computadoras: DTM

Sobre la cinta tengo escrito el input que es un string de
sımbolos de Σ a partir de la celda 1, y el resto de las celdas
tiene ∗ (blancos).
Definimos un programa S como un conjunto de qu ́
ıntuplas
S ⊆ Q × Γ × Q × Γ × M, donde M = {+1, −1} son los
movimientos de la cabeza a derecha o izquierda.
Para todo par (qi , sj ), existe exactamente una qu ́
ıntupla que
comienza con ese par (maquina determinıstica).
Optimizacion :: DM, FCEyN, UBA

Clases de complejidad computacional: P y NP

Modelos de Computadoras
NP-completitud
Maquina de Turing Determinıstica
Maquina de Turing No Determinıstica
Modelos de Computadoras: DTM
¿Que significa la que
ıntupla (qi , sh , qj , sk , +1)? Significa que si
estando en el estado qi la cabeza lee sh , entonces escribe sk ,
se mueve a la derecha y pasa al estado qj .
La complejidad de una DTM esta dada por la cantidad de
movimientos de la cabeza en funcion del tamaño de la


entrada.
Un problema esta en P si existe una DTM de

complejidad polinomial que lo resuelve.
Existen otros modelos de computadoras determin sticas
(maquina de Turing con varias cintas, Random Access
Machines, etc.) pero puede probarse que son equivalentes en
terminos de la polinomialidad de los problemas a la DTM.

Optimizacion :: DM, FCEyN, UBA

Clases de complejidad computacional: P y NP


Modelos de Computadoras
NP-completitud
Maquina de Turing Determinıstica
Maquina de Turing No Determinıstica
Modelos de Computadoras: NDTM
Maquinas de Turing No Determinısticas (NDTM)
No se pide unicidad de la quıntupla que comienza con
cualquier par (qi , sj ).

En caso de que hubiera mas de una quıntupla, la maquina se
replica continuando cada una por una rama distinta.
Decimos que una NDTM resuelve el problema π si para toda
instancia de Yπ existe una rama que llega a un estado final qsi
y para toda instancia en Dπ \ Yπ ninguna rama llega a un
estado final qsi .

Optimizacion :: DM, FCEyN, UBA

Clases de complejidad computacional: P y NP


Modelos de Computadoras
NP-completitud
Maquina de Turing Determinıstica
Maquina de Turing No Determinıstica
Modelos de Computadoras: NDTM
Una NDTM es polinomial para π cuando existe una funcion
polinomial T (n) de manera que para toda instancia de Yπ de
tamaño n, alguna de las ramas termina en estado qsi en a lo
sumo T (n) pasos.

Un problema π ∈ NP si existe una NDTM polinomial
que resuelve π.
Equivalentemente, un problema π ∈ NP si para toda instancia
en Yπ , existe un “certificado” que puede ser verificado en
tiempo polinomial. En el caso de TSP, el certificado consiste
en un circuito Hamiltoniano de longitud ≤ k. Es facil ver que
puede verificarse en tiempo polinomial si es un circuito
Hamiltoniano y si su longitud es ≤ k.
Claramente, P ⊆ NP. Conjetura: P = NP.

Optimizacion :: DM, FCEyN, UBA

Clases de complejidad computacional: P y NP

Modelos de Computadoras
NP-completitud
Maquina de Turing Determinıstica
Maquina de Turing No Determinıstica
Modelos de Computadoras: NDTM
Dado un problema π, se define su problema complemento π
como aquel tal que Dπ = Dπ e Yπ = Dπ \ Yπ .
Ejemplo: π = ¿Es p primo?; π = ¿Es p compuesto?.
Un problema π ∈ co-NP si π ∈ NP.
Claramente, P ⊆ co-NP.

Optimizacion :: DM, FCEyN, UBA

Clases de complejidad computacional: P y N

Modelos de Computadoras
NP-completitud
¿P = NP?
Problemas NP-completos
NP-completitud
Reduccion polinomial: Sean π y π dos problemas de
decision. Decimos que f : Dπ → Dπ es una reduccion
polinomial de π en π si f se computa en tiempo polinomial y
para todo d ∈ Dπ , d ∈ Yπ ⇔ f (d) ∈ Yπ . Notacion: π

π.
Notemos que si π
π yπ
π entonces π
π, ya que la
composicion de dos reducciones polinomiales es una reduccion
polinomial.

Un problema π es NP-completo si:
1. π ∈ NP.
2. Para todo π ∈ NP, π
π.
Si un problema π verifica la condicion 2., π es NP-Hard (es al
menos tan “difıcil” como todos los problemas de NP).

Optimizacion :: DM, FCEyN, UBA

Clases de complejidad computacional: P y NP


Modelos de Computadoras
NP-completitud
¿P = NP?
Problemas NP-completos
¿P = NP? La pregunta del millon...

Si existe un problema en NP-c ∩ P, entonces P=NP.
Si π ∈ NP-c ∩ P, existe un algoritmo polinomial que resuelve
π, por estar π en P. Por otro lado, como π es NP-completo,
para todo π ∈ NP, π
π.
Sea π ∈ NP. Apliquemos la reduccion polinomial que
transforma instancias de π en instancias de π y luego el
algoritmo polinomial que resuelve π. Por definicion de
reduccion polinomial, es facil ver que lo que se obtiene es un
algoritmo polinomial que resuelve π .
Hasta el momento no se conoce ningun problema en NP-c ∩
P, asi como tampoco se ha demostrado que un problema
esta en NP \ P. En ese caso
 
¿Como se prueba que un problema es NP-completo?

El problema SAT consiste en decidir si, dada una formula logica φ
expresada como conjuncion de disyunciones (ej:
φ = x1 ∧ (x2 ∨ ¬x1 ) ∧ (x3 ∨ ¬x4 ∨ x1 )), existe una valuacion de sus
variables qu haga verdadera φ.
Es facil ver que SAT ∈ NP. El certificado en este caso seria una
valuacion que satisfaga φ. Evaluar una formula es polinomial.o
Teorema de Cook (1971): SAT es NP-completo.

La demostracion de Cook es directa: considera un problema
generico π ∈ NP y una instancia generica d ∈ Dπ . A partir de la
hipotetica NDTM que resuelve π, genera en tiempo polinomial una
formula logica φπ,d en forma normal (conjuncion de disyunciones)
tal que d ∈ Yπ si y solo si φπ,d es satisfactible.

Optimizacion :: DM, FCEyN, UBA

Clases de complejidad computacional: P y NP

Modelos de Computadoras
NP-completitud
¿P = NP?
Problemas NP-completos
¿Como se prueba que un problema es NP-completo?
A partir del Teorema de Cook, la tecnica standard para probar que
un problema π es NP-completo aprovecha la transitividad de , y
consiste en lo siguiente:
1. Mostrar que π esta en NP.

2. Elegir un problema π apropiado que se sepa que es
NP-completo.
3. Construir una reduccion polinomial f de π en π.

La segunda condicion en la definicion de problema NP-completo
sale usando la transitividad: sea π un problema cualquiera de NP.
Como π es NP-completo, π
π . Como probamos que π
π,
resulta π
π.

Optimizacion :: DM, FCEyN, UBA

Clases de complejidad computacional: P y NP


Modelos de Computadoras
NP-completitud
¿P = NP?
Problemas NP-completos
Reduccion de SAT a 3-SAT

El problema 3-SAT es una variante del problema SAT, en el cual
cada clausula tiene exactamente tres literales. Como es una
restriccion del dominio de SAT, esta en NP, y en principio es “no
mas difıcil que SAT.
Para probar que 3-SAT es NP-completo, vamos entonces a reducir
SAT a 3-SAT.
Tomemos una instancia generica de SAT φ = C1 ∧ · · · ∧ Cm .

Vamos a reemplazar cada Ci por una conjuncion de disyunciones
φi , donde cada disyuncion tenga tres literales, y de manera que φ
sea satisfactible si y solo si φ1 ∧ · · · ∧ φm lo es.

Optimizacion :: DM, FCEyN, UBA

Clases de complejidad computacional: P y NP
Introduccion
Modelos de Computadoras
NP-completitud
¿P = NP?
Problemas NP-completos
Reduccion de SAT a 3-SAT

Si Ci tiene tres literales, queda como esta.
Ci tiene menos de tres literales, agregamos nuevas variables
como en el ejemplo:
(x1 ∨ ¬x2 ) → (x1 ∨ ¬x2 ∨ y ) ∧ (x1 ∨ ¬x2 ∨ ¬y )
Si Ci tiene cuatro o mas literales, agregamos nuevas variables

como en el ejemplo:
(x1 ∨ ¬x2 ∨ x3 ∨ x4 ∨ ¬x5 ) →
(x1 ∨ ¬x2 ∨ y1 ) ∧ (¬y1 ∨ x3 ∨ y2 ) ∧ (¬y2 ∨ x4 ∨ ¬x5 )
Queda como ejercicio escribir formalmente la reduccion y
demostrar que es una reducci ́n polinomial de SAT a 3-SAT.








Biblografia: www.di.uniovi.es/~dani/asignaturas/transparencias-leccion19.PDF