Problemas NP-completos
Profa. Sandra de Amo
Teoria da Computação
Pós-graduação em Ciência da
Computação
Diagrama das Reduções entre os Problemas
SAT
3-SAT
CLIQUE
VC
VC = Vertex Cover
HAMCIRC
UHAMCIRC
CV = Caixeiro Viajante
CV
HAMPATH
UHAMPATH
SUM-SET
Mochila
K-COLOR
Coloração de Grafos
• Input: Grafo G = (V,E) , não dirigido, inteiro K ≤ |V|
• Pergunta: G é k-colorável, isto é, existe uma função
f: V  {1,2,...,K}
tal que f(u) ≠ f(v) sempre que {u,v} ϵ E ?
K=2
K=3
???
Problema da K-coloração de grafos
• K ≥ 3 : NP-Completo Karp 1972 : 3SAT  K-color
• K=2 : polinomial
• K=4 : todo grafo planar pode ser colorido com 4
cores.
– 1879: Alfred Kempe deu primeira prova
– 1890: encontrado um erro na prova de Kempe
– 1890: idéias de Kempe utilizadas para mostrar a 5-coloração de
grafos planares (Percy John Heawood)
– 1976: Kenneth Appel/Wolfgang Haken – prova por computador
HAMPATH é NP-completo
Input: Grafo G = (V,E) , dirigido, s,t  V
Pergunta: Existe caminho hamiltoniano ligando os vértices s e t ?
Caminho hamiltoniano: passa uma única vez por todos os vértices do
grafo
3-SAT
≤
1. HAMPATH é NP
HAMPATH
2. 3-SAT
≤p
HAMPATH
Redução polinomial
3-SAT
HAMPATH
Variáveis = {x1, x2, ..., xl}
F é satisfatível
F = (a1 V b1 V c1) ^ (a2 V b2 V c2) ^ ... ^ (ak V bk V ck)
Grafo G, vértices s, t
Existe caminho
Hamiltoniano ligando
sat
Construção do grafo G: estruturas básicas
Para cada variável x construímos uma estrutura de “diamante”
com 4 + M vértices
Para cada cláusula C construímos um vértice extra
...
M vértices
M = 3k + 1
k = nº de cláusulas
Juntando as estruturas
C1
x1
C2
x2
C3
.
.
.
Ck
.
.
.
xl
Como ligar os dois tipos de estruturas
x1
C1 = x1 V x4 V ¬ x5
C1
...
C1
Como ligar os dois tipos de estruturas
C1 = x1 V x4 V ¬ x5
x5
C1
...
C1
Resumo
• Um diamante só está ligado a vértices externos
correspondendo a cláusulas onde sua variável
aparece.
• Os vértices internos “brancos” e “azuis” dos
diamantes não estão ligados a vértices externos.
• Os vértices “verdes” e “vermelhos” dos
diamantes estão ligados aos vértices externos
(cláusulas) onde eles aparecem.
Se F é satisfatível então existe
caminho hamiltoniano de s a t
• Cada cláusula Ci contém ao menos um literal Li verdadeiro.
• Escolhemos este literal verdadeiro para cada cláusula Ci.
• Li = xj ou Lj = ¬xj
s
O caminho hamiltoniano
ligando os vértices s a t vai
percorrer os diamantes fazendo
desvios para os vértices externos e voltando
para o mesmo diamante
x1
.
.
.
x2
xj
Os diamantes correspondentes aos literais escolhidos vão conter “desvios”
para as cláusulas onde eles foram selecionados
C1
...
V(xj) = F
C1
O diamante é percorrido em zig-zag ou zag-zig, dependendo se a variável
é avaliada como verdadeira ou falsa.
• Todos os vértices dos diamantes são
visitados uma única vez.
• Todos os vértices externos são visitados:
– O vértice Ci é visitado uma única vez
quando se percorre o diamante
correspondente ao literal Li que foi escolhido
como verdadeiro para Ci.
Se existe caminho Hamiltoniano
ligando s a t então F é satisfatível.
• Caso 1: o caminho hamiltoniano percorre os diamantes de forma
normal, isto é:
– na ordem em que aparecem fazendo desvios para os vértices externos e
retornando para o mesmo diamante de onde saiu o desvio.
Avaliação de variáveis:
• V(xi) = True se o diamante é percorrido em zig-zag
• V(xi) = False se o diamante é percorrido em zag-zig
É claro que V(F) = True:
Seja Ci cláusula de F.
– Se Ci é percorrido em zig-zag é porque a variável xj de onde saiu o desvio
(em zig-zag) aparece como positiva em Ci. Logo V(Ci) = true.
– Se Ci é percorrido em zag-zig é porque a variável xj de onde saiu o desvio
(em zag-zig) aparece como negativa em Ci. Logo V(Ci) = true.
Caso 2: O caminho hamiltoniano percorre os
diamantes de forma anormal:
u
v
C1
C1
ISTO NÃO PODE OCORRER !
t
...
Como percorrer o vértice v ?
- chegando de u ? Não !
- chegando de t ? Para
onde ir depois disto ? Só
poderia ir para u, mas este
já foi percorrido !
...
C1
SUM-SET é NP-completo
Input: S = {n1,...,np}  N , t  N
Pergunta: Existe subconjunto S’  S tal que Σ i = t ?
i  S’
3-SAT
≤
1. SUM-SET é NP
SUM-SET
2. 3-SAT
≤p
SUM-SET
Redução polinomial
3-SAT
SUM-SET
Variáveis = {x1, x2, ..., xl}
F é satisfatível
F = (a1 V b1 V c1) ^ (a2 V b2 V c2) ^ ... ^ (ak V bk V ck)
S = {n1,...,nk}  N , t  N
Existe subconjunto
S’  S tal que Σ i = t ?
i  S’
Um par y,z para cada variável x
Um par g,h para cada
cláusula C
1
2 3
4
y1 1
z1 1
0 0
l
C1
C2
0
0
0
0
0
0
0
0
0
0
...
...
0
0
n1
0 0
1 0
1 0
1
0
0
1
1
0
...
...
0
0
n3
n4
y3 0
z3 0
.
.
.
0 1
0 1
0
0
0
0
1
0
1
0
...
...
0
1
n5
n6
yl
zl
0 0
0 0
y2 0
z2 0
0
0
...
1
Ck
n2
S
0
0
1
1
g1
h1
g2
h2
.
.
gk
hk
t
...
1
1
1
...
1
0
0
0
0
...
...
0
0
1
0
...
0
1
0
...
0
1
...
0
1
...
0
..
1
1
3
3
...
3
n7
np
Se F é satisfatível então existe
subconjunto S’ de S com soma = t
1. Se F é satisfatível, existe avaliação de variáveis V tal que V(F) = True.
2. Para cada variável xi:
V(xi) = true ou V(xi) = false.
3. Para cada i = 1,...,l :
– Se V(xi) = true, considere a linha yi
– Se V(xi) = false, considere a linha zi
4. Como F é satisfatível, então V(Cj) = true para toda cláusula Cj, j = 1,...,k
• Logo, para todo j = 1,...,k, existe um literal verdadeiro em Cj.
• Logo, toda coluna j = 1,...,k, contém pelo menos uma célula em uma das linhas
escolhidas em (3). Esta célula contém um 1.
• Como cada cláusula só tem 3 literais, então cada coluna j = 1,...,k tem no máximo 3
células nas linhas escolhidas em (3).
5. Para cada coluna j = 1,...,k completa-se com 0, 1 ou 2 linhas da parte
bottom-right da tabela, dependendo se tem 3, 2, ou 1 célula nas linhas
escolhidas em (3).
6. O conjunto S` = conjunto das linhas consideradas em (3) e em (5)
Se existe subconjunto S’ de S com
soma = t então F é satisfatível
1. Se a soma resulta em 3 para cada coluna de j = 1,...,k (da parte top-right),
então em cada coluna da parte top-right, ao menos uma linha de S’ que
colabora para esta soma está na parte top-right da tabela.
2. Como a soma das colunas da parte esquerda é 1, conclui-se que S’ não
contém duas linhas yi e zi.
3. Associamos o valor verdade True para cada literal com valor 1 aparecendo
nas linhas de S’ da parte de cima da tabela.
4. A partir de (1) concluimos que cada cláusula possui um literal verdadeiro.
Logo V(F) = True.
5. Portanto F é satisfatível.
Um par y,z para cada variável x
Um par g,h para cada
cláusula C
1
2 3
4
y1 1
z1 1
y2 0
z2 0
0 0
l
C1
C2
0
0
0
0
0
0
0
0
0
0
...
...
0
0
n1
0 0
1 0
1 0
1
0
0
1
1
0
...
...
0
0
n3
n4
y3 0
z3 0
.
.
.
0 1
0 1
0
0
0
0
1
1
...
0
0
0
...
1
n5
n6
yl
zl
0 0
0 0
0
0
...
1
Ck
n2
S
0
0
1
1
g1
h1
g2
h2
.
.
gk
hk
t
...
1
1
1
...
1
0
0
1
0
...
...
0
0
1
0
...
0
1
0
...
0
1
...
0
1
...
0
..
1
1
3
3
...
3
n7
np
UHAMPATH é NP-Completo
• Input: Grafo não dirigido G, s, t vértices de G
• Pergunta: Existe caminho hamiltoniano em G,
começando em s e terminando em t ?
HAMPATH
≤
1. UHAMPATH é NP
UHAMPATH
2. HAMPATH ≤pUHAMPATH
Redução polinomial
G= Grafo dirigido G, s,t vértices de G
HAMPATH
UHAMPATH
G’ = Grafo não- dirigido G,
s´,t´ vértices de G
Existe caminho hamiltoniano
em G ligando s a t
Existe caminho hamiltoniano
em G´ ligando s´ a t´
(G,s,t)  (G’,s´,t´)
s
u
umid
sout
uin
vin
v
uout
vout
t
vmid
GRAFO DIRIGIDO G
tin
GRAFO Não - DIRIGIDO G´
• Suponhamos que existe caminho
hamiltoniano em G ligando s a t
u
v
S
t
umid
uin
uout
S out
t in
vin
vmid
vout
umid
uin
Por que não seria um Vout ?
uout
Sout
tin
vin
vout
vmid
u
v
S
t