Aula 24 de Teoria da Computação (NP-completude - Exemplos)

Prévia do material em texto

Teoria da
Computac¸a˜o
116360
Aula 24
Roteiro
NP-
completude:
exemplos
Exerc´ıcio:
Conjunto
Independente
(IS)
Exerc´ıcio:
Circuito
Hamiltoniano
(HC)
Roteiro da Aula 24
1 NP-completude: exemplos
Clique
Situac¸a˜o atual
Cobertura de Ve´rtices (Vertex Cover)
Conjunto Dominante (Dominating Set)
2 Exerc´ıcio: Conjunto Independente (IS)
3 Exerc´ıcio: Circuito Hamiltoniano (HC)
Teoria da
Computac¸a˜o
116360
Aula 24
Roteiro
NP-
completude:
exemplos
Clique
Situac¸a˜o atual
Cobertura de
Ve´rtices (Vertex
Cover)
Conjunto
Dominante
(Dominating
Set)
Exerc´ıcio:
Conjunto
Independente
(IS)
Exerc´ıcio:
Circuito
Hamiltoniano
(HC)
Clique
Instaˆncia: grafo G = (V,E) e inteiro positivo k
• Vamos reduzir 3SAT a Clique:
• Dada uma 3CNF-fo´rmula φ, constru´ımos em tempo
polinomial, um grafo G e um k, tal que:
φ e´ satisfat´ıvel sse G possui uma clique de tamanho k
Teoria da
Computac¸a˜o
116360
Aula 24
Roteiro
NP-
completude:
exemplos
Clique
Situac¸a˜o atual
Cobertura de
Ve´rtices (Vertex
Cover)
Conjunto
Dominante
(Dominating
Set)
Exerc´ıcio:
Conjunto
Independente
(IS)
Exerc´ıcio:
Circuito
Hamiltoniano
(HC)
Clique
φ = (x1 ∨ x2 ∨ x3) ∧ (x1 ∨ x2 ∨ x3) ∧ (x1 ∨ x2 ∨ x3) ∧ (x1 ∨ x2 ∨ x3)
x1 x2 x3
x2 x3x1
x1
x2
x3
x1
x2
x3
C1
C2
C3
C4
Teoria da
Computac¸a˜o
116360
Aula 24
Roteiro
NP-
completude:
exemplos
Clique
Situac¸a˜o atual
Cobertura de
Ve´rtices (Vertex
Cover)
Conjunto
Dominante
(Dominating
Set)
Exerc´ıcio:
Conjunto
Independente
(IS)
Exerc´ıcio:
Circuito
Hamiltoniano
(HC)
Clique
φ = (x1 ∨ x2 ∨ x3) ∧ (x1 ∨ x2 ∨ x3) ∧ (x1 ∨ x2 ∨ x3) ∧ (x1 ∨ x2 ∨ x3)
x1 x2 x3
x2 x3x1
x1
x2
x3
x1
x2
x3
C1
C2
C3
C4
Teoria da
Computac¸a˜o
116360
Aula 24
Roteiro
NP-
completude:
exemplos
Clique
Situac¸a˜o atual
Cobertura de
Ve´rtices (Vertex
Cover)
Conjunto
Dominante
(Dominating
Set)
Exerc´ıcio:
Conjunto
Independente
(IS)
Exerc´ıcio:
Circuito
Hamiltoniano
(HC)
Clique
φ = (x1 ∨ x2 ∨ x3) ∧ (x1 ∨ x2 ∨ x3) ∧ (x1 ∨ x2 ∨ x3) ∧ (x1 ∨ x2 ∨ x3)
x1 x2 x3
x2 x3x1
x1
x2
x3
x1
x2
x3
C1
C2
C3
C4
Teoria da
Computac¸a˜o
116360
Aula 24
Roteiro
NP-
completude:
exemplos
Clique
Situac¸a˜o atual
Cobertura de
Ve´rtices (Vertex
Cover)
Conjunto
Dominante
(Dominating
Set)
Exerc´ıcio:
Conjunto
Independente
(IS)
Exerc´ıcio:
Circuito
Hamiltoniano
(HC)
Clique
φ = (x1 ∨ x2 ∨ x3) ∧ (x1 ∨ x2 ∨ x3) ∧ (x1 ∨ x2 ∨ x3) ∧ (x1 ∨ x2 ∨ x3)
x1 x2 x3
x2 x3x1
x1
x2
x3
x1
x2
x3
C1
C2
C3
C4
Teoria da
Computac¸a˜o
116360
Aula 24
Roteiro
NP-
completude:
exemplos
Clique
Situac¸a˜o atual
Cobertura de
Ve´rtices (Vertex
Cover)
Conjunto
Dominante
(Dominating
Set)
Exerc´ıcio:
Conjunto
Independente
(IS)
Exerc´ıcio:
Circuito
Hamiltoniano
(HC)
Clique
φ = (x1 ∨ x2 ∨ x3) ∧ (x1 ∨ x2 ∨ x3) ∧ (x1 ∨ x2 ∨ x3) ∧ (x1 ∨ x2 ∨ x3)
x1 x2 x3
x2 x3x1
x1
x2
x3
x1
x2
x3
C1
C2
C3
C4
• Se φ tem 4 cla´usulas, enta˜o G tem uma clique de
tamanho 4, se e somente se φ e´ satisfat´ıvel.
Teoria da
Computac¸a˜o
116360
Aula 24
Roteiro
NP-
completude:
exemplos
Clique
Situac¸a˜o atual
Cobertura de
Ve´rtices (Vertex
Cover)
Conjunto
Dominante
(Dominating
Set)
Exerc´ıcio:
Conjunto
Independente
(IS)
Exerc´ıcio:
Circuito
Hamiltoniano
(HC)
Situac¸a˜o atual
P
NP
NP-Completo
SAT
3SAT
Clique
Teoria da
Computac¸a˜o
116360
Aula 24
Roteiro
NP-
completude:
exemplos
Clique
Situac¸a˜o atual
Cobertura de
Ve´rtices (Vertex
Cover)
Conjunto
Dominante
(Dominating
Set)
Exerc´ıcio:
Conjunto
Independente
(IS)
Exerc´ıcio:
Circuito
Hamiltoniano
(HC)
Cobertura de Ve´rtices (Vertex Cover)
1 2
3
5 7
6
4
1 2
3
5 7
6
4
• Dado um grafo na˜o-direcionado G = (V,E) e um natural
k, decidir se existe um subconjunto dos ve´rtices de G,
Vc ⊆ V , |Vc| = k, tal que:
• Para toda aresta (a, b) ∈ E:
• a ∈ Vc; ou
• b ∈ Vc.
Teoria da
Computac¸a˜o
116360
Aula 24
Roteiro
NP-
completude:
exemplos
Clique
Situac¸a˜o atual
Cobertura de
Ve´rtices (Vertex
Cover)
Conjunto
Dominante
(Dominating
Set)
Exerc´ıcio:
Conjunto
Independente
(IS)
Exerc´ıcio:
Circuito
Hamiltoniano
(HC)
Cobertura de Ve´rtices (Vertex Cover)
1 2
3
5 7
6
4
1 2
3
5 7
6
4
Cobertura M´ınima
• Dado um grafo na˜o-direcionado G = (V,E) e um natural
k, decidir se existe um subconjunto dos ve´rtices de G,
Vc ⊆ V , |Vc| = k, tal que:
• Para toda aresta (a, b) ∈ E:
• a ∈ Vc; ou
• b ∈ Vc.
Teoria da
Computac¸a˜o
116360
Aula 24
Roteiro
NP-
completude:
exemplos
Clique
Situac¸a˜o atual
Cobertura de
Ve´rtices (Vertex
Cover)
Conjunto
Dominante
(Dominating
Set)
Exerc´ıcio:
Conjunto
Independente
(IS)
Exerc´ıcio:
Circuito
Hamiltoniano
(HC)
Cobertura de Ve´rtices (Vertex Cover)
Mas VC e´ NP-completo tambe´m... como mostrar?
Teoria da
Computac¸a˜o
116360
Aula 24
Roteiro
NP-
completude:
exemplos
Clique
Situac¸a˜o atual
Cobertura de
Ve´rtices (Vertex
Cover)
Conjunto
Dominante
(Dominating
Set)
Exerc´ıcio:
Conjunto
Independente
(IS)
Exerc´ıcio:
Circuito
Hamiltoniano
(HC)
Cobertura de Ve´rtices (Vertex Cover)
Mas VC e´ NP-completo tambe´m... como mostrar?
• Vamos reduzir Clique a VC;
Teoria da
Computac¸a˜o
116360
Aula 24
Roteiro
NP-
completude:
exemplos
Clique
Situac¸a˜o atual
Cobertura de
Ve´rtices (Vertex
Cover)
Conjunto
Dominante
(Dominating
Set)
Exerc´ıcio:
Conjunto
Independente
(IS)
Exerc´ıcio:
Circuito
Hamiltoniano
(HC)
Cobertura de Ve´rtices (Vertex Cover)
Mas VC e´ NP-completo tambe´m... como mostrar?
• Vamos reduzir Clique a VC;
• Reduc¸a˜o claramente polinomial: Dada instaˆncia para
clique G = (V,E), k, construa a instaˆncia
G = (V,E), |V | − k para VC.
• G possui cobertura de tamanho |V | − k sse G possui
clique de tamanho k. Por queˆ?
Teoria da
Computac¸a˜o
116360
Aula 24
Roteiro
NP-
completude:
exemplos
Clique
Situac¸a˜o atual
Cobertura de
Ve´rtices (Vertex
Cover)
Conjunto
Dominante
(Dominating
Set)
Exerc´ıcio:
Conjunto
Independente
(IS)
Exerc´ıcio:
Circuito
Hamiltoniano
(HC)
Conjunto Dominante (Dominating Set)
1 2
3
5 7
6
4
• Dado um grafo na˜o-direcionado G = (V,E) e um natural
k, decidir se existe um subconjunto dos ve´rtices de G,
Vc ⊆ V , |Vc| = k, tal que:
• Para todo ve´rtice v ∈ V :
• v ∈ Vc; ou
• existe aresta (a, v) ∈ E e a ∈ Vc.
Teoria da
Computac¸a˜o
116360
Aula 24
Roteiro
NP-
completude:
exemplos
Clique
Situac¸a˜o atual
Cobertura de
Ve´rtices (Vertex
Cover)
Conjunto
Dominante
(Dominating
Set)
Exerc´ıcio:
Conjunto
Independente
(IS)
Exerc´ıcio:
Circuito
Hamiltoniano
(HC)
Conjunto Dominante (Dominating Set)
1 2
3
5 7
6
4
• Dado um grafo na˜o-direcionado G = (V,E) e um natural
k, decidir se existe um subconjunto dos ve´rtices de G,
Vc ⊆ V , |Vc| = k, tal que:
• Para todo ve´rtice v ∈ V :
• v ∈ Vc; ou
• existe aresta (a, v) ∈ E e a ∈ Vc.
Teoria da
Computac¸a˜o
116360
Aula 24
Roteiro
NP-
completude:
exemplos
Clique
Situac¸a˜o atual
Cobertura de
Ve´rtices (Vertex
Cover)
Conjunto
Dominante
(Dominating
Set)
Exerc´ıcio:
Conjunto
Independente
(IS)
Exerc´ıcio:
Circuito
Hamiltoniano
(HC)
Conjunto Dominante (Dominating Set)
1 2
3
5 7
6
4
• Dado um grafo na˜o-direcionado G = (V,E) e um natural
k, decidir se existeum subconjunto dos ve´rtices de G,
Vc ⊆ V , |Vc| = k, tal que:
• Para todo ve´rtice v ∈ V :
• v ∈ Vc; ou
• existe aresta (a, v) ∈ E e a ∈ Vc.
Teoria da
Computac¸a˜o
116360
Aula 24
Roteiro
NP-
completude:
exemplos
Clique
Situac¸a˜o atual
Cobertura de
Ve´rtices (Vertex
Cover)
Conjunto
Dominante
(Dominating
Set)
Exerc´ıcio:
Conjunto
Independente
(IS)
Exerc´ıcio:
Circuito
Hamiltoniano
(HC)
Conjunto Dominante (Dominating Set)
1 2
3
5 7
6
4
Conjunto Dominante M´ınimo
• Dado um grafo na˜o-direcionado G = (V,E) e um natural
k, decidir se existe um subconjunto dos ve´rtices de G,
Vc ⊆ V , |Vc| = k, tal que:
• Para todo ve´rtice v ∈ V :
• v ∈ Vc; ou
• existe aresta (a, v) ∈ E e a ∈ Vc.
Teoria da
Computac¸a˜o
116360
Aula 24
Roteiro
NP-
completude:
exemplos
Clique
Situac¸a˜o atual
Cobertura de
Ve´rtices (Vertex
Cover)
Conjunto
Dominante
(Dominating
Set)
Exerc´ıcio:
Conjunto
Independente
(IS)
Exerc´ıcio:
Circuito
Hamiltoniano
(HC)
Conjunto Dominante (Dominating Set)
Mas DS e´ NP-completo tambe´m... como mostrar?
Teoria da
Computac¸a˜o
116360
Aula 24
Roteiro
NP-
completude:
exemplos
Clique
Situac¸a˜o atual
Cobertura de
Ve´rtices (Vertex
Cover)
Conjunto
Dominante
(Dominating
Set)
Exerc´ıcio:
Conjunto
Independente
(IS)
Exerc´ıcio:
Circuito
Hamiltoniano
(HC)
Conjunto Dominante (Dominating Set)
Mas DS e´ NP-completo tambe´m... como mostrar?
• Vamos reduzir VC a DS.
Teoria da
Computac¸a˜o
116360
Aula 24
Roteiro
NP-
completude:
exemplos
Exerc´ıcio:
Conjunto
Independente
(IS)
Exerc´ıcio:
Circuito
Hamiltoniano
(HC)
Exerc´ıcio: Conjunto Independente (IS)
Mostre que o seguinte problema e´ NP-completo
1 2
3
5 7
6
4
• Dado um grafo na˜o-direcionado G = (V,E) e um natural
k, decidir se existe um subconjunto dos ve´rtices de G,
Vc ⊆ V , |Vc| = k, tal que:
• Se a ∈ Vc e b ∈ Vc, enta˜o (a, b) 6∈ Vc
Teoria da
Computac¸a˜o
116360
Aula 24
Roteiro
NP-
completude:
exemplos
Exerc´ıcio:
Conjunto
Independente
(IS)
Exerc´ıcio:
Circuito
Hamiltoniano
(HC)
Caminho Hamiltoniano (HP) e´ NP-completo
Ha´ uma reduc¸a˜o muito interessante
de 3SAT para HP no Sipser
Vale a pena conferir...
Teoria da
Computac¸a˜o
116360
Aula 24
Roteiro
NP-
completude:
exemplos
Exerc´ıcio:
Conjunto
Independente
(IS)
Exerc´ıcio:
Circuito
Hamiltoniano
(HC)
Exerc´ıcio: Circuito Hamiltoniano (HC)
Mostre que o seguinte problema e´ NP-completo
1 2
3
5 7
6
4
• Dado um grafo na˜o-direcionado G = (V,E), decidir se
existe um circuito hamiltoniano em G. Quer dizer, uma
permutac¸a˜o (x1, x2, x3, . . . , xn) dos ve´rtices, tal que:
• (xi, xi+1) ∈ E, 1 ≤ i ≤ n− 1; e
• (xn, x1) ∈ E.
DICA: reduza HP a HC
Teoria da
Computac¸a˜o
116360
Aula 24
Roteiro
NP-
completude:
exemplos
Exerc´ıcio:
Conjunto
Independente
(IS)
Exerc´ıcio:
Circuito
Hamiltoniano
(HC)
Exerc´ıcio: Circuito Hamiltoniano (HC)
Mostre que o seguinte problema e´ NP-completo
1 2
3
5 7
6
4
• Dado um grafo na˜o-direcionado G = (V,E), decidir se
existe um circuito hamiltoniano em G. Quer dizer, uma
permutac¸a˜o (x1, x2, x3, . . . , xn) dos ve´rtices, tal que:
• (xi, xi+1) ∈ E, 1 ≤ i ≤ n− 1; e
• (xn, x1) ∈ E.
DICA: reduza HP a HC
Teoria da
Computac¸a˜o
116360
Aula 24
Roteiro
NP-
completude:
exemplos
Exerc´ıcio:
Conjunto
Independente
(IS)
Exerc´ıcio:
Circuito
Hamiltoniano
(HC)
Situac¸a˜o atual
P
NP
NP-Completo
SAT
3SAT
Clique
VC
DS
IS
HP
HC
PRIMES
PRIMES
?
?
	Roteiro
	NP-completude: exemplos
	Clique
	Situação atual
	Cobertura de Vértices (Vertex Cover)
	Conjunto Dominante (Dominating Set)
	Exercício: Conjunto Independente (IS)
	Exercício: Circuito Hamiltoniano (HC)