Agenda
•• Conceitos
Conceitos básicos
básicos
•• Classes
Classes de
de Complexidade
Complexidade
–– PP
–– NP
NP
•• Redução
Redução
•• Problemas
Problemas NPC
NPC
Análise e Técnicas de Algoritmos
Jorge Figueiredo
NP-Completude
NP-Completude
© Jorge Figueiredo, DSC/UFCG
Análise e Técnicas de Algoritmos – 2005.1
© Jorge Figueiredo, DSC/UFCG
Análise e Técnicas de Algoritmos – 2005.1
Introdução
Eficiência
•Existem
•Existem alguns
alguns problemas
problemas computacionais
computacionais que
que são
são difíceis
difíceis de
de
serem
serem resolvidos.
resolvidos.
•Impossível
•Impossível de
de se
se provar
provar que
que não
não existe
existe solução
solução eficiente.
eficiente.
•Que
•Que conclusões
conclusões tirar
tirar da
da tabela
tabela abaixo?
abaixo?
•• Como
Como definir
definir aa eficiência
eficiência de
de uma
uma solução?
solução?
–– Vimos
Vimos em
em nosso
nosso curso
curso aa conveniência
conveniência de
de se
se utilizar
utilizar
medidas
medidas de
de complexidade
complexidade como
como medida
medida de
de eficiência.
eficiência.
•• Um
Um algoritmo
algoritmo éé eficiente
eficiente quando
quando aa sua
sua complexidade
complexidade for
for
polinomial
polinomial em
em relação
relação ao
ao tamanho
tamanho de
de sua
sua entrada.
entrada.
k
–– Um
Um algoritmo
algoritmo éé dito
dito ser
ser de
de tempo
tempo polinomial
polinomial se
se for
for O(n
O(nk),),
para
alguma
constante
k
>
0.
para alguma constante k > 0.
–– Qualquer
Qualquer outro
outro algoritmo
algoritmo que
que não
não for
for polinomial
polinomial éé dito
dito ser
ser
exponencial.
exponencial.
–– Classificação
Classificação não
não éé absoluta.
absoluta.
–– Algumas
Algumas vezes
vezes pode
pode ser
ser insatisfatória
insatisfatória mas,
mas,na
na maioria
maioria dos
dos
casos,
casos,éé aceitável.
aceitável.
Funções de
Complexidade
Tamanho da Entrada (n)
10
20
30
40
50
60
n
.00001s
.00002s
.00003s
.00004s
.00005s
.00006s
n2
.0001s
.0004s
.0009s
.0016s
.0025s
.0036s
n3
.001s
.008s
.027s
.064s
.125s
.216s
n5
.1s
3.2s
24.3s
1.7min
5.2min
13.0min
2n
.001s
1.0s
17.9min
12.7dias 35.7anos
3n
0.059s
58min
6.5anos
2855sec 2x108 sec 1.3x1013sec
Análise e Técnicas de Algoritmos – 2005.1
366sec
© Jorge Figueiredo, DSC/UFCG
© Jorge Figueiredo, DSC/UFCG
Análise e Técnicas de Algoritmos – 2005.1
Intratabilidade de Problemas
NP-Completude
•• Um
Um problema
problema éé dito
dito tratável
tratável se
se ele
ele apresenta
apresenta uma
uma solução
solução
polinomial.
polinomial.
•• Um
Um problema
problema éé intratável
intratável se
se ele
ele for
for tão
tão difícil
difícil que
que nenhum
nenhum
algoritmo
algoritmo polinomial
polinomial pode
pode resolvê-lo.
resolvê-lo.
•• Alguns
Alguns algoritmos
algoritmospolinomiais
polinomiais podem
podem não
não ser
ser muito
muito úteis.
úteis.Por
Por
100
exemplo,
exemplo, se
se for
for O(n
O(n100).). Na
Na prática,
prática, porém,
porém, quase
quase sempre
sempre os
os
polinômios
polinômios são
são de
de grau
grau 22 ou
ou 3.
3.
•• Alguns
Alguns problemas
problemas são
são tão
tão difíceis
difíceis que
que são
são indecidíveis.
indecidíveis. Por
Por
exemplo,
exemplo, oo problema
problema da
da parada.
parada.
•• Por
Por outro
outro lado,
lado, alguns
alguns problemas
problemas são
são decidíveis
decidíveis mas,
mas,
intratáveis.
intratáveis.
•• Vamos
Vamos estudar
estudar certos
certos problemas
problemas que
que são,
são, de
defato,
fato, difíceis
difíceis
(computacionalmente)
(computacionalmente) de
de se
se resolver.
resolver.
•• Esse
Esse ééaa idéia
idéia central
central da
da teoria
teoria de
de NP-Completude.
NP-Completude.
•• Vamos
Vamos mostrar
mostrar que
que encontrar
encontrar uma
uma solução
solução eficiente
eficiente para
para um
um
certo
certo problema
problema éé tão
tão difícil
difícil quanto
quanto encontrar
encontrar soluções
soluções
eficientes
eficientes para
para todos
todos os
os problemas
problemas definidos
definidos em
em uma
uma classe
classe
de
de problemas
problemas que
que chamamos
chamamos NP.
NP.
Análise e Técnicas de Algoritmos – 2005.1
© Jorge Figueiredo, DSC/UFCG
Análise e Técnicas de Algoritmos – 2005.1
© Jorge Figueiredo, DSC/UFCG
1
Problema Algorítmico
Classes de Problemas
•• Caracterizado
Caracterizado por:
por:
–– Conjunto
Conjunto de
de dados.
dados.
–– Objetivo
Objetivo do
do problema.
problema.
–– Solução.
Solução.
•• Exemplo:
Exemplo: Encontrar
Encontrar um
um clique
clique de
de tamanho
tamanho kk em
em um
um grafo
grafo G.
G.
–– Conjunto
Conjunto de
dedados:
dados: um
umgrafo
grafoG
Geeum
uminteiro
inteiro kk >> 0.
0.
–– Objetivo
Objetivo do
do problema:
problema: aa própria
própria definição.
definição.
•• Problemas
Problemas de
de Decisão:
Decisão: Problemas
Problemas em
em que
que aa saída
saída (solução)
(solução)
éé SIM
SIMou
ou NÃO.
NÃO.
•• Problemas
Problemas de
de Localização:
Localização: Determinar
Determinar uma
uma certa
certa estrutura
estrutura
que
que satisfaça
satisfaça um
um conjunto
conjunto de
de propriedades
propriedades dadas.
dadas.
•• Problemas
Problemas de
de Otimização:
Otimização: Problemas
Problemas de
de localização
localização em
em que
que
as
as propriedades
propriedades satisfazem
satisfazem critérios
critériosde
de otimização.
otimização.
© Jorge Figueiredo, DSC/UFCG
Análise e Técnicas de Algoritmos – 2005.1
Classes de Problemas
Análise e Técnicas de Algoritmos – 2005.1
© Jorge Figueiredo, DSC/UFCG
Classes de Complexidade P e NP
•• ÉÉ possível
possível relacionar
relacionar problemas
problemas de
de otimização
otimização ee localização
localização
com
com problemas
problemas de
de decisão.
decisão. Por
Por exemplo:
exemplo:
Problema
Problema de
de Decisão:
Decisão:
Dados:
Dados: Um
Umgrafo
grafoG
Geeum
um inteiro
inteiro k>0.
k>0.
Objetivo:
Objetivo: Verificar
Verificar se
se G
G possui
possui um
um percurso
percurso de
de caixeiro
caixeiro
viajante
viajante de
de peso
peso ≤k.
≤k.
Problema
Problema de
de Localização:
Localização:
Dados:
Dados: Um
Umgrafo
grafo G
Geeum
um inteiro
inteiro k>0.
k>0.
Objetivo:
Objetivo: Localizar,
Localizar, em
em G,
G, um
um percurso
percurso de
de caixeiro
caixeiro viajante
viajantede
de
peso
peso ≤k.
≤k.
Problema
Problema de
de Otimização:
Otimização:
Dados:
Dados: Um
Um grafo
grafo G.
G.
Objetivo:
Objetivo: Localizar,
Localizar, em
em G,
G, um
um percurso
percurso de
de caixeiro
caixeiro viajante
viajante
ótimo.
ótimo.
© Jorge Figueiredo, DSC/UFCG
Análise e Técnicas de Algoritmos – 2005.1
•• Todos
Todos os
os problemas
problemas que
que vamos
vamos utilizar
utilizar no
no estudo
estudo de
de NPNPCompletude
Completude são
são problemas
problemas de
de decisão.
decisão.
•• AA Classe
Classe de
de Complexidade
Complexidade PP(polynomial
(polynomial time)
time) éé oo conjunto
conjunto
de
de todos
todos os
os problemas
problemas de
de decisão
decisão que
que são
são resolvíveis
resolvíveis em
em
tempo
tempo polinomial
polinomial em
em um
umcomputador
computador determinístico.
determinístico.
•• AA Classe
Classe de
de Problemas
Problemas NP
NP (nondeterministic
(nondeterministic polynomial
polynomial
time)
time) éé oo conjunto
conjunto de
de problemas
problemas resolvíveis
resolvíveis em
em tempo
tempo
polinomial
polinomial em
em um
um computador
computador não-determinístico.
não-determinístico. AA Classe
Classe
NP
NP também
também pode
pode ser
ser definida
definida como
como aa classe
classe de
de problemas
problemas em
em
que
que éé possível
possível verificar
verificar em
emtempo
tempo polinomial,
polinomial, se
se um
um
determinada
determinada solução
solução proposta
proposta satisfaz
satisfaz oo problema
problema de
de decisão.
decisão.
Análise e Técnicas de Algoritmos – 2005.1
© Jorge Figueiredo, DSC/UFCG
Não Determinismo
Classes de Complexidade Co-NP
•• Veja
Veja um
um computador
computador não
não determinístico
determinístico como
comosendo
sendo um
um
computador
computador que
que “magicamente
“magicamente adivinha”
adivinha” uma
uma solução:
solução:
–– Se
Se aa solução
solução existe,
existe, oo computador
computador sempre
sempre adivinha.
adivinha.
•• Outra
Outra forma
forma de
de definir:
definir: Um
Um computador
computador paralelo
paralelo que
que executa
executa
infinito
infinito número
número de
de processos
processos
–– Um
Um processador
processador para
para cada
cada solução
solução possível
possível
O
O complemento
complemento de
de um
um problema
problema de
de decisão
decisão DD éé um
um problema
problema
de
de decisão
decisão cujo
cujo objetivo
objetivo éé oo complemento
complemento da
da decisão
decisão de
de D.
D.
AA Classe
Classe Co-NP
Co-NP compreende
compreende exatamente
exatamente os
os complementos
complementos dos
dos
problemas
problemas da
da classe
classe NP.
NP.
Análise e Técnicas de Algoritmos – 2005.1
© Jorge Figueiredo, DSC/UFCG
Análise e Técnicas de Algoritmos – 2005.1
© Jorge Figueiredo, DSC/UFCG
2
Relação entre Classes de Complexidade
Relação entre Classes de Complexidade
•• PP == conjunto
conjunto de
de problemas
problemas que
que podem
podem ser
ser resolvidos
resolvidos em
em
tempo
tempo polinomial
polinomial
•• NP
NP ==conjunto
conjunto de
de problemas
problemas cuja
cuja solução
solução pode
pode ser
ser verificada
verificada
em
em tempo
tempo polinomial
polinomial
•• PP ⊆⊆ NP
NP
•• Questão
Questão não
não resolvida:
resolvida: PP== NP?
NP? ou
ouPP≠≠ NP?
NP?
•• Se
Se PP≠≠ NP
NP,, NP
NP ––PP são
são problemas
problemas intratáveis.
intratáveis.
Análise e Técnicas de Algoritmos – 2005.1
© Jorge Figueiredo, DSC/UFCG
Alguns Problemas de Decisão em NP
Problema
Problema 1:
1: Satisfiability
Satisfiability
•• O
O problema
problema da
da satisfiability
satisfiability(SAT)
(SAT) éé um
um problema
problema de
de lógica
lógica
que
que envolve
envolve expressões
expressões booleanas.
booleanas.Pode
Pode ser
ser definido
definido da
da
seguinte
seguinte forma:
forma:
–– Dados:
Dados: Uma
Uma expressão
expressão booleana
booleana EEna
na sua
sua forma
forma normal
normal
conjuntiva
conjuntiva (FNC).
(FNC).
–– Objetivo:
Objetivo: Verificar
Verificar se
se EE éé satisfeita,
satisfeita, ou
ou seja,
seja, verificar
verificar se
se
existe
existe uma
uma atribuição
atribuição de
de valores
valores às
às variáveis
variáveis da
da expressão
expressão
de
de tal
tal modo
modo que
que aa expressão
expressão seja
seja avaliada
avaliada verdadeira.
verdadeira.
Uma
Uma expressão
expressão éé FNC
FNC quando
quando for
for uma
uma conjunção
conjunção de
de cláusulas.
cláusulas.
Por
Por exemplo,
exemplo, (x2∨¬x1)∧(x1∨¬x3∨¬x2)∧(x3)∧(x1∨x3∨x2).
(x2∨¬x1)∧(x1∨¬x3∨¬x2)∧(x3)∧(x1∨x3∨x2).
Análise e Técnicas de Algoritmos – 2005.1
© Jorge Figueiredo, DSC/UFCG
Análise e Técnicas de Algoritmos – 2005.1
© Jorge Figueiredo, DSC/UFCG
Alguns Problemas de Decisão em NP
Problema
Problema 2:
2: Conjunto
ConjuntoIndependente
Independente de
de Vértices
Vértices
•• Dados:
Dados: Um
Um grafo
grafo G
G ee um
um inteiro
inteiro k>0.
k>0.
•• Objetivo:
Objetivo: Verificar
Verificar se
se G
G possui
possui um
um conjunto
conjunto independente
independente de
de
vértices
vértices de
de tamanho
tamanho ≥k.
≥k.
Dado
Dado um
um grafo
grafo G=
G= (V,E),
(V,E),um
umconjunto
conjuntoindependente
independentede
devértices
vértices
⊆ V tal que qualquer par de vértices de
éé um
um subconjunto
subconjunto VVIND
IND ⊆ V tal que qualquer par de vértices de
não é adjacente.
VVIND
IND não é adjacente.
Análise e Técnicas de Algoritmos – 2005.1
© Jorge Figueiredo, DSC/UFCG
Alguns Problemas de Decisão em NP
Alguns Problemas de Decisão em NP
Problema
Problema 3:
3: Clique
Clique
•• Dados:
Dados: Um
Um grafo
grafo G
G ee um
um inteiro
inteiro k>0.
k>0.
•• Objetivo:
Objetivo: Verificar
Verificar se
se G
G possui
possui um
um clique
clique de
de tamanho
tamanho ≥k.
≥k.
Dado
⊆V
Dado um
um grafo
grafo G=
G= (V,E),
(V,E),um
umclique
cliqueééum
umsubconjunto
subconjunto VVCLI
CLI ⊆ V
tal
é
adjacente.
tal que
que qualquer
qualquer par
par de
de vértices
vértices de
de VVCLI
é
adjacente.
CLI
Problema
Problema 4:
4: Cobertura
Cobertura de
de Vértices
Vértices
•• Dados:
Dados: Um
Um grafo
grafo G
G ee um
um inteiro
inteiro k>0.
k>0.
•• Objetivo:
Objetivo: Verificar
Verificar se
se G
G possui
possui uma
uma cobertura
cobertura de
de vértices
vértices de
de
tamanho
tamanho ≤k.
≤k.
Dado
Dado um
um grafo
grafo G=
G= (V,E),
(V,E),uma
umacobertura
coberturade
de vértices
vértices ééum
um
⊆ V tal que qualquer aresta de G é
subconjunto
subconjunto VVCOB
COB ⊆ V tal que qualquer aresta de G é
.
incidente
incidente aa um
um vértice
vértice de
de VVCOB
COB.
Análise e Técnicas de Algoritmos – 2005.1
© Jorge Figueiredo, DSC/UFCG
Análise e Técnicas de Algoritmos – 2005.1
© Jorge Figueiredo, DSC/UFCG
3
Alguns Problemas de Decisão em NP
Problema
Problema 5:
5: Coloração
Coloração
•• Dados:
Dados: Um
Um grafo
grafo G
G ee um
um inteiro
inteiro k>0.
k>0.
•• Objetivo:
Objetivo: Verificar
Verificar se
se G
G possui
possui uma
uma coloração
coloração com
com um
umnúmero
número
de
de cores
cores ≤k.
≤k.
Dado
Dado um
um grafo
grafo G=
G= (V,E),
(V,E),uma
umacoloração
coloraçãoééatribuída
atribuídaaa G
Gde
detal
tal
forma
forma que
que dois
dois vértices
vérticesadjacentes
adjacentes tenham
tenham cores
cores distintas.
distintas.
Análise e Técnicas de Algoritmos – 2005.1
© Jorge Figueiredo, DSC/UFCG
Problemas NP-Completos
•A
•Aclasse
classede
deproblemas
problemasNP
NPcaptura
capturaooconjunto
conjuntode
deproblemas
problemasque
que
acreditamos
acreditamosque
quesejam
sejamdifíceis
difíceisde
dese
setratar.
tratar.
•Existem,
•Existem,entretanto,
entretanto,problemas
problemasque
quepodem
podemser
serconsiderados
consideradospelo
pelomenos
menos
tão
tãodifíceis
difíceiscomo
comoqualquer
qualqueroutro
outroem
emNP.
NP.
•Essa
•Essaclasse
classede
deproblemas
problemasmais
maisdifíceis
difíceisem
emNP
NPééchamada
chamadade
deNP-Completo
NP-Completo
ou
ouNPC.
NPC.
© Jorge Figueiredo, DSC/UFCG
Análise e Técnicas de Algoritmos – 2005.1
Redução em Tempo Polinomial
Teorema de Cook
•• Um
Um problema
problema PP pode
pode ser
ser reduzido
reduzido aa um
um outro
outro problema
problema Q
Qse
se
qualquer
qualquer instância
instância de
de PP pode
pode ser
ser refraseada
refraseada (transformada)
(transformada)
para
para uma
uma instância
instância de
de Q.
Q.
•• Intuitivamente:
Intuitivamente: se
sePP éé redutível
redutível em
em tempo
tempo polinomial
polinomial aa Q,
Q,PP
não
não éé mais
mais difícil
difícilde
de resolver
resolver do
do que
que Q.
Q.
•• SAT
SATéé NP-Completo.
NP-Completo.
•• SAT
SATtem
tem aapropriedade
propriedade que
que todos
todos os
os problemas
problemas em
em NP
NP
podem
podem ser
ser reduzidos
reduzidos aa ele,
ele, em
emtempo
tempo polinomial.
polinomial.
•• Existem
Existem outros
outros problems
problems em
em NP
NP que
que têm
têm as
as mesmas
mesmas
características
características de
deSAT.
SAT.
•• Se
Se D1
D1 ∈∈ NPC
NPC ee D2
D2 ∈∈ NPC,
NPC, então
então D1
D1 ≤≤pp D2
D2 ee D2
D2 ≤≤pp D1.
D1.
•• ÉÉ possível
possível concluir:
concluir:
–– Se
Se um
um problema
problema NPC
NPC pode
pode ser
ser resolvido
resolvido em
em tempo
tempo
polinomial,
polinomial, então
então todos
todos os
os problemas
problemas de
de NP
NP podem
podem sê-lo.
sê-lo.
–– Se
Se um
um problema
problema de
de NP
NP éé intratável,
intratável, todos
todos os
os problemas
problemas
de
de NPC
NPC são
são intratáveis.
intratáveis.
Análise e Técnicas de Algoritmos – 2005.1
© Jorge Figueiredo, DSC/UFCG
Como Determinar se um Problema é NPC?
•• Se
Se P,
P,Q
Q ∈∈NP,
NP,PP éé NPC
NPC ee PP ≤≤ppQ,
Q,então
então Q
Q éé NP-Completo.
NP-Completo.
•• Para
Para provar
provar se
se um
um problema
problema de
de decisão
decisão DD éé NP-Completo,
NP-Completo,
devemos
devemos seguir
seguir os
os seguintes
seguintes passos:
passos:
1.
Mostra
que
D
∈
NP.
1. Mostra que D ∈ NP.
2.
2. Selecionar,
Selecionar, D1,
D1, um
um problema
problema NPC
NPC conhecido.
conhecido.
3.
3. Achar
Achar uma
uma redução
redução de
de D1
D1 ≤≤pp DDpara
para ..
4.
4. Mostrar
Mostrar que
que aa redução
redução foi
foi feita
feita em
emtempo
tempo polinomial.
polinomial.
Análise e Técnicas de Algoritmos – 2005.1
© Jorge Figueiredo, DSC/UFCG
Análise e Técnicas de Algoritmos – 2005.1
© Jorge Figueiredo, DSC/UFCG
Exemplos de Problemas NPC: 3SAT
•• O
O problema
problema 3SAT
3SATconsiste
consiste em
em determinar
determinar oo resultado
resultado de
de uma
uma
expressão
expressão booleana
booleana EE que
que está
está escrita
escrita em
em sua
sua FNC
FNC éé
satisfeita.
satisfeita.
•• Cada
Cada cláusula
cláusula de
de EEtem
tem exatamente
exatamente três
três literais.
literais.Por
Por
exemplo:
exemplo:
––
(v1
(v1 ∨∨ ¬v2
¬v2 ∨∨ v7)∧(v3
v7)∧(v3 ∨∨ v5
v5 ∨∨ ¬v6)∧(v1
¬v6)∧(v1 ∨∨ ¬v5
¬v5 ∨∨ ¬v8)
¬v8) éé
uma
uma instância
instância de
de 3SAT.
3SAT.
•• Aplicando
Aplicando os
os passos
passos para
para determinar
determinar se
se 3SAT
3SATééNPC
NPC temos:
temos:
–– 3SAT
3SATéé claramente
claramente NP.
NP.
–– SAT
SATéé NPC.
NPC. Se
SeSAT
SAT≤≤pp 3SAT.
3SAT. (vamos
(vamos mostrar
mostrar como
como aa
redução
redução éé feita)
feita)
–– Se
Se aa redução
redução éé feita
feita em
em tempo
tempo polinomial,
polinomial, 3SAT
3SATéé NPC.
NPC.
Análise e Técnicas de Algoritmos – 2005.1
© Jorge Figueiredo, DSC/UFCG
4
3SAT
Cobertura de Vértices é NPC
Para
Para fazer
fazer aa redução,
redução, devemos
devemos substituir
substituir cada
cada cláusula
cláusula Ci
Ci em
em EE
por:
por:
–– Se
Se Ci=(a)
Ci=(a) ,, devemos
devemos trocar
trocar por
por Si
Si ==
(a∨b∨c)∧(a∨¬b∨c)∧(a∨b∨¬c)∧(a∨¬b∨¬c)
(a∨b∨c)∧(a∨¬b∨c)∧(a∨b∨¬c)∧(a∨¬b∨¬c) ..
–– Se
Se Ci=(a∨b),
Ci=(a∨b), devemos
devemos trocar
trocar por
por Si
Si== (a∨b∨c)
(a∨b∨c) ∧(a∨b∨¬c)
∧(a∨b∨¬c)
–– Se
Se Ci=
Ci= (a∨b∨c),
(a∨b∨c), não
não fazemos
fazemos nada.
nada.
–– Se
Se Ci=
Ci= (a
(a11∨a
∨a22∨...∨a
∨...∨akk),),k>3,
k>3, devemos
devemos trocar
trocar por
por Si
Si ==
(a
∨a k-1∨a
(a11∨a
∨a22∨b
∨b11)∧(¬b
)∧(¬b11∨a
∨a33∨b
∨b22)∧(¬b
)∧(¬b22∨a
∨a44∨b
∨b33)∧...∧(¬b
)∧...∧(¬bk-3
∨akk)) ..
k-3∨ak-1
–– As
As variáveis
variáveis adicionadas
adicionadas são
são novas
novas variáveis
variáveis que
que não
não
estão
estão sendo
sendo usadas.
usadas.
•• Reduzir
Reduzir 3SAT
3SATpara
para Cobertura
Cobertura de
de Vértices:
Vértices:
–– Para
Para cada
cada variável
variável xxcrie
crie um
um nó
nó para
para xxee ¬x
¬xee conecte
conecte os
os
dois
dois nós.
nós.
–– Para
Para cada
cada cláusula
cláusula (a∨b∨c),
(a∨b∨c), crie
crie um
umtriângulo
triângulo ee conecte
conecte
os
os 33 nós.
nós.
© Jorge Figueiredo, DSC/UFCG
Análise e Técnicas de Algoritmos – 2005.1
a
x
x
y
¬y
z
b
© Jorge Figueiredo, DSC/UFCG
Cobertura de Vértices é NPC
Complete
Completeaaconstrução:
construção:
–– Conecte
Conectecada
cadaliteral
literalem
emum
umtriângulo
triângulopara
paraooseu
seu
correspondente
correspondente(no
(nopar).
par).
–– Seja
n
o
número
de
variáveis,
m
o
número
de
Seja n o número de variáveis, m o número decláusulas
cláusulas
–– Fazer
Fazerkk==nn++2m
2m
–– Por
Porexemplo,
exemplo,(¬x∨y∨z)
(¬x∨y∨z)
¬x
c
Análise e Técnicas de Algoritmos – 2005.1
Cobertura de Vértices é NPC
••
¬x
•• Exemplo:
Exemplo: (a∨b∨c)∧(¬a∨b∨¬c)∧(¬b∨¬c∨¬d)
(a∨b∨c)∧(¬a∨b∨¬c)∧(¬b∨¬c∨¬d)
•• O
O Grafo
Grafo tem
tem cobertura
cobertura de
de vértice
vértice de
de tamanho
tamanho kk == 4+6
4+6 ==10
10
sss
sssaafórmula
fórmula éé satisfatível
satisfatível
a
¬a
b
¬b
c
¬c
d
¬d
¬z
12
22
32
a
c
b
11
© Jorge Figueiredo, DSC/UFCG
Análise e Técnicas de Algoritmos – 2005.1
Análise e Técnicas de Algoritmos – 2005.1
13
21
23
31
33
© Jorge Figueiredo, DSC/UFCG
Clique é NPC
•• Reduzir
Reduzir aa partir
partir de
de cobertura
cobertura de
de vértices.
vértices.
•• O
O grafo
grafo G
Gtem
tem cobertura
cobertura de
de vértice
vértice de
de tamanho
tamanho kk sss
sssseu
seu
complemento
complemento tem
tem um
um clique
clique de
de tamanho
tamanho n-k.
n-k.
G
Análise e Técnicas de Algoritmos – 2005.1
G’
© Jorge Figueiredo, DSC/UFCG
5