c b nuestro primer problema a np-completo5]cook.pdf · • problema: decidir si la fórmula es...

Complexity©D.Moshkovitz

1

Nuestro primer problemaNP-CompletoA

BC

El teorema de Cook-Levin

Complexity©D.Moshkovitz

2

Introducción

• Objetivos:– Presentar un problema NP-Completo

• Resumen:– Definición y ejemplos del problema SAT– El teorema de Cook-Levin– ¿Y después qué?

Complexity©D.Moshkovitz

3

SAT • Entrada: Una fórmula booleana.• Problema: Decidir si la fórmula es satisfactible.

)x(x)x )x x((x 231321 ∧¬∨¬∧¬∨∨F T

Una fórmula booleana satisfactible:

F TT T

Una fórmula booleana insatisfactible:11 xx ¬∧

Complexity©D.Moshkovitz

4

¿A qué clase de complejidad pertenece SAT?

SAT

Co-NP PNP

Complexity©D.Moshkovitz

5

SAT está en NP: Algoritmo no determinista

• Adivina una asignación de las variables.• Comprueba la asignación.

)x(x)x )x x((x 231321 ∧¬∨¬∧¬∨∨F T F TT T

x1

x2

x3

F

T

T

Complexity©D.Moshkovitz

6

El teorema de Cook-Levin: SAT es NP-Completo

SIP 254-259

Idea de la prueba: Por cada MTND M y cada entradaw, construimos una fórmula ϕM,w que essatisfactible sii M acepta w.

,M wϕ # 1 1 # 1

... ...

Complexity©D.Moshkovitz

7

Representación de un cómputo por medio de una tabla de configuraciones

nk

# ... # # ...

# #

q0 w1 wn_ # ... #

#...

# #

q0 w1 wn_ # ... #

#...

# #

q0 w1 wn_

Indica el final de la parte relevante de la cinta

El contenido de la parte relevante de la cintay la posición de la cabeza

nk

Cota superioren el tiempo de ejecución

Complexity©D.Moshkovitz

8

Tabla: Ejemplos

• TM:-Q={q0, qsi, qno}-Σ={1}-Γ={1,_ }-δ(q0,1)={(q0,_,D)}-δ(q0,_)={(qsi,I)}

• TM:-Q={q0, qsi, qno}-Σ={1}-Γ={1,_ }-δ(q0,1)={(q0,_,D)}-

• tabla (entrada 11)

δ(q0,_)={(qsi,I)}

# q0 1 1 _ #

# _ q0 1 _ #

# _ 1 q0 _ #

# _ qsi _ _ #

• tabla (entrada 11)

¿Qué hace estamáquina?

Complexity©D.Moshkovitz

9

Las variables de la fórmula

xi, j, s

# ... ##

.

.

.

# #

símbolo (s∈Γ∪Q∪{#})

semántica: “¿s es elcontenido de la casilla(i,j)?”

Posición en la tabla (1≤i,j≤nk)

Complexity©D.Moshkovitz

10

ϕ

La fórmula ϕ

M,w = φcell ∧ φstart ∧ φmove ∧ φacceptϕM,w = φcell ∧ φstart ∧ φmove ∧ φaccept

contenido de las casillas consistente

la máquina acepta

entrada consistente transiciones legales

Complexity©D.Moshkovitz

11

Un único símbolo en cada casilla

∨∧

= ∧∨∧

∈≠∈≤≤

)xx(xφ tj,i,sj,i,Cts

sj,i,Csnji,1

cellk

la casilla (i,j) contiene al menos un símbolo

no puede contener dos símbolos diferentes

Nota: la longitud de esta fórmula es polinómica en n

Complexity©D.Moshkovitz

12

La configuración inicial se corresponde con la entrada

Observación: podemos dar explícitamente el contenido de las casillas en el primer paso,sabiendo que la entrada es la palabra w1w2...wn,

k k0 1start 1,2,q 1,3,w 1,n 3,_1,1,# 1,n 1,_ 1,n ,#φ x x x ... x ... x x+ −= ∧ ∧ ∧ ∧ ∧ ∧ ∧

Complexity©D.Moshkovitz

13

La máquina acepta

El estado aceptador es visitado en algún momento durante la ejecución.

acceptk

qj,i,nji,1

accept xφ ∨≤≤

=

Complexity©D.Moshkovitz

14

Las transiciones son legales

# ... ##

.

.

.

# #

Local: sólo necesitamos mirar

2×3 casillas =ventana

Complexity©D.Moshkovitz

15

¿Qué ventanas son legales en este ejemplo?

1 q0 1

1 1 q0

_ q0 1

_ _ q0

1 q0 _

qsi _ _

# q0 1

# _ q0

1 q0 1

1 _ q0

• TM:– Q={q0,qsi,qno}– Σ={1}– Γ={1,_}– δ(q0,1)={(q0,_,R)}– δ(q0,_)={(qsi,L)}

• TM:– Q={q0,qsi,qno}– Σ={1}– Γ={1,_}– δ(q0,1)={(q0,_,R)}– δ(q0,_)={(qsi,L)}

1 q0 1

qsi _ _

Complexity©D.Moshkovitz

16

Las transiciones son legales

( )61 a1,j1,iaj,1,imove x...xφ ++−

≤≤

∧∧∨= ∧61 ,...,,1 aanji k

para cada a1,...,a6 t.q.forman una ventana

a1 a2 a3

a4 a5 a6

Complexity©D.Moshkovitz

17

ϕ

La fórmula completa

M,w = φcell ∧ φstart ∧ φmove ∧ φacceptϕM,w = φcell ∧ φstart ∧ φmove ∧ φaccept

ϕM,w

- tiene un tamaño polinómico en n ¡Comprobarlo!

- es satisfactible si y sólo si la máquina M acepta la entrada w.

Complexity©D.Moshkovitz

18

Conclusión: SAT es NP-Completo

Para cada lenguaje A en NP,

se reduce a... Comprobar si unafórmula es

satisfactibleComprobar si unapalabra está en A

Complexity©D.Moshkovitz

19

Co-NP NP P

NPC

SAT

Volviendo al plano

Complexity©D.Moshkovitz

20

El camino por delante

A partir de ahora, para probar que un problema de NP es NP-Completo, simplementenecesitamos reducir SAT a él.cualquierproblemade NP

se reduce a ...

SAT

Implicaría que el nuevo problema está en NPC

se reduce a...Teorema de Cook-Levin problema

de NP nuevo

Complexity©D.Moshkovitz

21

... ¡Y más allá!

Más aún, cada problema NP-Completo que descubramos, se convierte en un camino para probar que otros de NP son NP-Completos.

cualquierproblema

de NP se reduce a...

problemaNP-Hard conocido problema

de NP nuevo

se reduce a...

Complexity©D.Moshkovitz

22

Resumen

• Hemos probado que SAT es NP-Completo.• Hemos descrito un método general para

probar que otros problemas también sonNP-Completos.