AED II - Introdução à Teoria do NP-Completo

Prévia do material em texto

1
Introdução à
Teoria do NP-Completo
Notas de aula da disciplina IME 04-05441
ALGORITMOS (Organização de Dados)
Paulo Eustáquio Duarte Pinto
(pauloedp arroba ime.uerj.br)
dezembro/2008
COMPORTAMENTO ASSINTÓTICO DE FUNÇÕES
São formas matemáticas de expressar, simplifica-
damente, a quantidade de execuções da instrução 
mais executada em um algoritmo, em função do 
crescimento da entrada.
Introdução à Teoria do NP-Completo
n0
f
c.g
n
t
COMPORTAMENTO ASSINTÓTICO DE FUNÇÕES
Função O
Função Ω
Função Θ
Função o
Função ω
Introdução à Teoria do NP-Completo
Def: Dadas duas funções f e g sobre N, diz-se 
que f é O(g), se existirem c e n0 positivos tal que, 
n > n0 ⇒⇒⇒⇒ f(n) ≤ c.g(n).
Função O (limite superior)
n0
f
c.g
n
t
Introdução à Teoria do NP-Completo
Exemplos:
f(n) = 10.log2n + 5n
f é O(n), ou seja g(n) = n, pois, para n > 2,
f(n) = 10.log2n + 5n ≤≤≤≤ 10n + 5n = 15n = 15.g(n).
f(n) = aonk + a1nk-1 + ... + akn0
f é O(nk), ou seja g(n) = nk, pois, para n > 0,
f(n) ≤≤≤≤ c.nk = c.g(n), onde c = |ao|+|a1|+...+|ak|.
Introdução à Teoria do NP-Completo
ORDEM DE GRANDEZA - tempos de execução
0.00002
0.00001
0.00001
0.000007
0.000003
log n
---30 anos2.7 horas1.70.1100.000
---14 dias2 min0.130.0110.000
---17 min10.010.0011.000
1025
anos
10.010.00070.0001100
0.010.0010.00010.000030.0000110
2nn3n2n.log nnn\f(n) 
Introdução à Teoria do NP-Completo
2
Def: Dadas duas funções f e g sobre N, diz-se 
que f é Ω(g), se existirem c e n0 positivos tal que, 
n > n0 ⇒⇒⇒⇒ c.g(n) ≤ f(n).
Função Ω (limite inferior)
n0
f
c.g
n
t
Introdução à Teoria do NP-Completo
Exemplos:
f(n) = 10.log2n + 5n
f é Ω(log n), ou seja g(n) = log n pois, p/ n > 2, 
e qualquer a > 1,
f(n) = 10.log2n + 5n ≥ 10.log2n + 5.log2n = 
15.log2n = 15.log2a.loga n = c.g(n) 
f(n) = aonk + a1nk-1 + ... + akn0, com ai ≥ 0
f é Ω(nk), ou seja g(n) = nk pois, para n > 0,
f(n) ≥ c.nk = c.g(n), onde c = min1≤i≤nai.
Introdução à Teoria do NP-Completo
Def: Dadas duas funções f e g sobre N, diz-se 
que f é Θ(g), se existirem c1, c2 e n0 positivos tal 
que, n > n0 ⇒⇒⇒⇒ c2.g(n) ≥ f(n) ≥ c1.g(n).
Função Θ (limite assintótico firme)
n0
f
c1g
c2g
n
t
Introdução à Teoria do NP-Completo
Exemplo:
f é Θ(nk), ou seja g(n) = nk pois, para n > 0,
c1.nk ≤ f(n) ≤ c2.nk , onde 
c1 = min1≤i≤nai.
c2 = ∑0≤i≤kai.
f(n) = aonk + a1nk-1 + ... + akn0, com ai ≥ 0
Introdução à Teoria do NP-Completo
Exercício:
Responder se a seguinte afirmativa é certa ou 
errada e justificar:
“Se f e g são funções tais que 
f = O(g) e g = Ω(f), então f = Θ(g)”.
Introdução à Teoria do NP-Completo
Limite inferior de problema
Def: Seja P um problema algorítmico, cuja entrada tem 
tamanho n > 0 e g uma função real positiva em n. Diz-
se que P tem um limite inferior ΩΩΩΩ(g) quando qualquer 
algoritmo αααα que resolva P tem complexidade mínima O(g).
Um algoritmo αααα0 com complexidade O(g) é um algoritmo 
ótimo.
Ex: P1 = encontrar o menor elemento do vetor V, de 
tamanho n.
P1 tem limite inferior ΩΩΩΩ(n), pois qualquer algoritmo 
para P1 tem que usar cada um dos n elementos pelo 
menos uma vez.
O seguinte algoritmo para P1 é ótimo:
m ←←←← V[1];
Para i de 2 a n: Se (V[i] < m) Então m ←←←← V[i]; Fp;
Imprimir m;
Introdução à Teoria do NP-Completo
3
Limite inferior de ordenação
Qualquer processo de ordenação baseado em 
comparações das chaves pode ser representado por uma 
árvore binária de decisão, cujas folhas são permutações 
dos elementos a ordenar.
Ex: Árvore de Decisão para ordenação por Inserção de 
3 elementos distintos
1:2
2:3
<1,2,3> 2:31:3
1:3
<1,3,2> <3,1,2> <3,2,1><2,3,1>
<2,1,3>
≤
≤ ≤
≤ ≤
>
> >
>>
Introdução à Teoria do NP-Completo
Limite inferior de ordenação
Teorema: “O limite inferior da ordenação usando 
comparações é n log n”.
Prova: A árvore de decisão de qualquer algoritmo de 
ordenação usando comparações tem no mínimo n! folhas 
e portanto 2n! -1 nós. A altura mínima dessa árvore é
log(2n!-1) = O(log nn) = O(n log n). 
Logo, qualquer algoritmo de ordenação tem que fazer, 
no pior caso, pelo menos O(n log n) comparações. Daí
segue-se que ΩΩΩΩ(n log n) é um limite inferior para o 
problema.
Obs: Pela aproximação de Stirling, temos:
n! = (2pipipipin)½(n/e)n(1 + ΘΘΘΘ(1/n))
Introdução à Teoria do NP-Completo
Problemas Polinomiais x Problemas exponenciais
Problemas polinomiais (tratáveis) são aqueles para os 
quais existem algoritmos cuja complexidade é
polinomial.
Exemplos:
-Ordenação de Dados
-Buscas e atualização em árvores
-Buscas em grafos
-Ciclos Eulerianos
-Problemas com solução gulosa, em geral
-Problemas com solução por Programação dinâmica em geral
-Programação linear
Um algoritmo é eficiente quando sua complexidade é um 
polinômio no tamanho de sua entrada.
Complexidades polinomiais:
O(n), O (n log n) O(n2) O(n50) !?
Introdução à Teoria do NP-Completo
Problemas exponenciais (intratáveis) são aqueles para os 
quais somente existem algoritmos com complexidade ex-
ponencial ou superior.
Exemplos:
-Torre de Hanoi
-Geração de Permutações
Complexidades exponenciais ou superiores:
..n
O(2n), O(n!), O(nn), O(2n )
Problemas Polinomiais x Problemas exponenciais
Introdução à Teoria do NP-Completo
Problemas ainda não classificados
Existe uma grande classe de problemas para os quais 
ainda não se sabe se existe algoritmo polinomial ou não.
Exemplos:
-Partição (Soma de subconjuntos)
-Mochila
-Empacotamento
-Programação inteira
-Caixeiro viajante
-Ciclo Hamiltoniano
-Coloração de vértices em grafos
-Satisfatibilidade
-Clique Máxima em grafos
-Conjunto independente máximo em grafos
Introdução à Teoria do NP-Completo
Classes de problemas combinatórios
Problemas combinatórios podem ser classificados quanto 
à sua forma.
-Problemas de Busca
-Problemas de Otimização
-Problemas de Decisão
Um mesmo problema pode ser proposto em qualquer uma 
das formas acima.
Introdução à Teoria do NP-Completo
4
Problemas de Busca
Nos problemas de Busca, deve-se exibir detalhada-
mente a solução procurada.
Exemplo:
Mochila com itens únicos, dados seus pesos.
Problema: 
Dados n itens com pesos (p1, ...pn), e uma mochila de capacidade 
M, exibir a combinação de itens que preencha totalmente a 
mochila.
Introdução à Teoria do NP-Completo
Problemas de Otimização
Nos problemas de Otimização, deve-se indicar um valor 
máximo ou mínimo procurado.
Exemplo: 
Mochila com itens únicos dados seus pesos e valores.
Problema: 
Dados n itens com pesos e valores respectivos (p1, v1), ...(pn, vn), 
e uma mochila de capacidade M, exibir a combinação de itens que 
obtém o valor máximo, preenchendo-se a mochila total ou 
parcialmente.
Introdução à Teoria do NP-Completo
Problemas de Decisão
Nos problemas de Decisão, a resposta é sempre SIM
ou NÃO.
Exemplo:
Mochila com itens únicos, dados seus pesos e valores.
Problema: 
Dados n itens com pesos e valores respectivos (p1, v1), ...(pn, vn), 
mochila de valor M, e um valor Q, existe uma combinação dos 
itens tal que seja possível preencher a mochila, total ou 
parcialmente, com um valor maior ou igual a Q?
Introdução à Teoria do NP-Completo
Classes P P P P e NPNPNPNP de Problemas de Decisão
A Classe PPPP é constituída dos Problemas de Decisão po-
linomiais, ou seja, aqueles problemas de decisão para os 
quais existe um algoritmo de complexidade polinomial.
A Classe NPNPNPNP é constituída dos Problemas de Decisão 
que têm CERTIFICADOS de tamanho polinomial em re-
lação à entrada, para a resposta SIM, tal que o 
certificado pode ser verificado por um algoritmo 
polinomial.
A Classe NPNPNPNP é uma tentativa de lidar com os proble-
mas ainda não classificados. Notar que nada é exigido
Em relação à resposta NÃO.
Introdução à Teoria do NP-Completo
Certificados
Um certificado é um conjunto de dados, de tamanho 
polinomial, que permite verificar, em tempo polinomial,
que uma resposta SIM dada ao problema de decisão 
está correta.
Exemplo: Mochila com peso e valor, itens únicos.
Problema: 
Dados n itens com pesos e valoresrespectivos (p1, v1),...(pn, vn), 
mochila de capacidade M, e um valor Q, existe uma combinação 
dos itens tal que seja possível preencher a mochila (total ou 
parcialmente), com um valor maior ou igual a Q?
Certificado: Uma combinação dos itens dados.
(para verificar se a resposta está correta, verifica-se se a soma 
dos itens do certificado é maior ou igual a Q. Isso pode ser feito 
em tempo polinomial).
Introdução à Teoria do NP-Completo
Exemplos de Problemas da classe NPNPNPNP
1) Obviamente: PPPP ⊆ ⊆ ⊆ ⊆ NPNPNPNP.
Problema Clique: 
Dado um grafo G e um inteiro k, G contém uma clique de tamanho 
maior ou igual a k?
Certificado: Um subconjunto de vértices de G.
(Para verificar se o certificado está correto, deve-se confirmar se 
o subconjunto tem, no mínimo k vértices e se todos os vértices são 
vizinhos entre sí em G. Isso pode ser feito em tempo polinomial, 
pois tem-se que verificar no máximo a existência de n(n-1)/2 
arestas).
2) Clique ∈∈∈∈ NPNPNPNP.
Introdução à Teoria do NP-Completo
5
Exemplos de Problemas da classe NPNPNPNP
Problema Conjunto Independente: 
Dado um grafo G e um inteiro k, G contém um conjunto 
independente de tamanho maior ou igual a k?
Certificado: Um subconjunto de vértices de G.
(Para verificar se o certificado está correto, deve-se confirmar se 
o subconjunto tem, no mínimo k vértices e se todos os vértices não 
são vizinhos entre sí em G. Isso pode ser feito em tempo polino-
mial, pois tem-se que verificar no máximo a inexistência de 
n(n-1)/2 arestas).
3) Conjunto Independente ∈∈∈∈ NPNPNPNP.
Introdução à Teoria do NP-Completo
Exemplos de Problemas da classe NPNPNPNP
Problema Ciclo Hamiltoniano: 
Dado um grafo G, G contém um ciclo Hamiltoniano?
Certificado: Uma permutação dos vértices de G.
(Para verificar se o certificado está correto, deve-se confirmar se 
õ certificado é uma permutação dos vértices de G e se, na 
sequência da permutação (considerada circular), cada vértice é
vizinho do anterior. Isso pode ser feito em tempo polinomial, pois 
tem-se que verificar a existência de n arestas).
4) Ciclo Hamiltoniano ∈∈∈∈ NPNPNPNP.
Introdução à Teoria do NP-Completo
Exercício:
Descrever um certificado que mostra que o 
problema Coloração pertence a NPNPNPNP.
Problema Coloração: 
Dado um grafo G e um inteiro k, G contém uma coloração própria 
de G com, no máximo, k cores?
Introdução à Teoria do NP-Completo
Exemplos de Problemas da classe NPNPNPNP
Problema Número Composto: 
Dado um número inteiro n, n é composto?
Certificado: Dois inteiros a e b, com a, b ≠≠≠≠ 1.
(Para verificar se o certificado está correto, deve-se verificar se 
a e b são inteiros positivos diferentes de 1 e se seu produto é
igual a n. Isso é feito em O(1).)
5) Número Composto ∈∈∈∈ NPNPNPNP.
Introdução à Teoria do NP-Completo
Exemplos de Problemas da classe NPNPNPNP
Problema Primo: 
Dado um número inteiro n, n é primo?
Certificado: C(k) = ( r; q1,C(q1), ... qt,C(qt) ), onde:
r é tal que rk-1 ≡≡≡≡ 1 mod k
rk-1/qi ≠≠≠≠ 1 mod k
q1.q2...qt = k-1
cada qi é primo.
(A verificação é baseada em Teoremas da Teoria dos Números. 
Esse teorema deve ser verificado, recursivamente, para cada qi. 
Seja l o tamanho de C(k). Pode-se mostrar que l ≤≤≤≤ 4 log2 k ).)
6) Primo ∈∈∈∈ NPNPNPNP.
Introdução à Teoria do NP-Completo
Exemplos de Problemas da classe NPNPNPNP
Problema Primo: 
Dado um número inteiro n, n é primo?
Em 2002, três indianos, Agrawal, Kayal e Saxtena,inventaram um 
algoritmo polinomial para testar a primalidade de um número 
inteiro, n.
Esse algoritmo, chamado AKS, tem complexidade O((log n)13). 
7) Primo ∈∈∈∈ PPPP.
Introdução à Teoria do NP-Completo
6
Exemplos de Problemas da classe NPNPNPNP
Def: 
Dados dois grafos G1 e G2, diz-se que G1 e G2 são isomorfos 
quando existe uma bijeção
f: V(G1) →→→→ V(G2) tal que (v,w) ∈∈∈∈ E(G1) sse (f(v), f(w)) ∈∈∈∈ E(G2).
8) Isomorfismo de Grafos ∈∈∈∈ NPNPNPNP.
Exemplo:
2
45
1
a
d
e
b
f
c
c6
b5
a4
e3
f2
d1
f
36
Introdução à Teoria do NP-Completo
Exemplos de Problemas da classe NPNPNPNP
Problema Isomorfismo de Grafos: 
Dados os grafos G1 e G2, eles são isomorfos?
Certificado: Uma bijeção f de V(G1) para V(G2).
(Para verificar se o certificado está correto, deve-se confirmar se 
f é bijeção e se G2 é subgrafo de G1. Isso pode ser feito em 
tempo polinomial, pois tem-se que verificar a existência de m 
arestas em G2).
8) Isomorfismo de Grafos ∈∈∈∈ NPNPNPNP.
Introdução à Teoria do NP-Completo
Exemplos de Problemas da classe NPNPNPNP
Problema Satisfatibilidade: 
Dada uma expressão booleana E, na forma normal conjuntiva, E é
satisfatível?
Expressão na forma normal conjuntiva:
Sejam e1,...en variávies booleanas. Cada ei é denominado literal. 
Uma cláusula é uma disjunção, isto é, uma expressão da forma 
e1 | e2 | ... ek (só usa | (OU), literais ou sua negação).
Uma expressão na forma normal conjuntiva é um conjunto de 
cláusulas ligadas por & (AND).
Ex: E = (e1 | e3) & (e1 | e2 | e3).
Uma expressão E é satisfatível, quando existe uma atribuição aos 
literais que torna a expressão verdadeira. No exemplo dado, E é
satisfatível, bastando fazer: e1 = V; e2 = V; e3 = F.
9) Satisfatibilidade ∈∈∈∈ NPNPNPNP.
Introdução à Teoria do NP-Completo
Exemplos de Problemas da classe NPNPNPNP
Problema Satisfatibilidade: 
Dada uma expressão booleana E, na forma normal conjuntiva, E é
satisfatível?
9) Satisfatibilidade ∈∈∈∈ NPNPNPNP.
Introdução à Teoria do NP-Completo
Certificado: Uma atribuição de valores para os literais.
(Para verificar se o certificado está correto, basta calcular E com 
os valores dados e verificar que o resultado seja V. Isso 
claramente pode ser feito em tempo polinomial).
Exemplos de Problemas da classe NPNPNPNP
Problema 2-SAT: 
Dada uma expressão booleana E, na forma normal conjuntiva, onde 
cada cláusula tem exatamente 2 literais, E é satisfatível?
10) 2-SAT ∈∈∈∈ PPPP.
Introdução à Teoria do NP-Completo
Este problema tem um algoritmo polinomial que consiste em se criar 
um grafo a partir das cláusulas e verificar se a mesma cláusula e 
sua negação aparecem em um mesmo componente do grafo.
Exemplos de Problemas da classe NPNPNPNP
Problema 3-SAT: 
Dada uma expressão booleana E, na forma normal conjuntiva, onde 
cada cláusula tem exatamente 3 literais, E é satisfatível?
11) 3-SAT ∈∈∈∈ NPNPNPNP.
Introdução à Teoria do NP-Completo
Certificado: Uma atribuição de valores para os literais.
(O problema é um caso particular de Satisfatibilidade.).
7
Exercício:
Escrever uma fórmula na FNC com 2 variáveis 
booleanas que não seja satisfatível.
Introdução à Teoria do NP-Completo
Exemplos de Problemas da classe NPNPNPNP
Problema Clique Máxima: 
Dado um grafo G e um inteiro k, a clique máxima de G possui 
exatamente k vértices?
12) Conjectura: Clique Máxima ∉∉∉∉ NPNPNPNP.
Introdução à Teoria do NP-Completo
Conjectura-se que qualquer algoritmo para resolver esse problema 
seja exponencial, porque o número de cliques de um grafo pode ser 
exponencial, no número de vértices.
Exemplos de Problemas da classe NPNPNPNP
Problema Caixeiro Viajante: 
Dado um inteiro k, um conjunto n de cidades c1, ...cn e uma matriz 
de valores dij, de distâncias entre as cidades, existe um percurso 
de caixeiro viajante de distância total ≤≤≤≤ k?
13) Caixeiro Viajante ∈∈∈∈ NPNPNPNP.
Introdução à Teoria do NP-Completo
Exemplo: n = 4.
2
4 3
1
04
403
1502
54201
4321d O percurso c1c2c4c3c1
Tem distância total =
2+1+4+4 = 11.
Portanto, se k = 11, a
resposta seria SIM, 
para a instância dada.
Exemplos de Problemas da classe NPNPNPNP
Problema Caixeiro Viajante: 
Dado um inteiro k, um conjunto n de cidades c1, ...cn e uma matriz 
de valores dij, de distâncias entre as cidades, existe um percurso 
de caixeiro viajante de distância total ≤≤≤≤ k?
13) Caixeiro Viajante ∈∈∈∈ NPNPNPNP.
Introdução à Teoria do NP-Completo
Certificado: Um percurso de caixeiro viajante.
(Para verificar se o certificado está correto, checar que ele é um 
percurso válido e basta calcular a distância total,somando as 
distâncias entre cidades vizinhas no percurso, com o auxílio da 
matriz dada e verificar se o total é igual ou inferior a k. Isso 
claramente pode ser feito em tempo polinomial).
Classe COCOCOCO----NPNPNPNP de Problemas de Decisão
A Classe COCOCOCO----NPNPNPNP é constituída dos Problemas de 
Decisão que têm CERTIFICADOS de tamanho polinomial 
em relação à entrada, para a resposta NÃO, tal que o 
certificado pode ser verificado por um algoritmo 
polinomial.
Introdução à Teoria do NP-Completo
COCOCOCO----NPNPNPNP NPNPNPNPPPPP
Primo Número Composto
Perguntas ainda não respondidas:
P = P = P = P = NP NP NP NP ???? P = COP = COP = COP = CO----NP NP NP NP ∩∩∩∩ NP NP NP NP ? ? ? ? NP = CONP = CONP = CONP = CO----NP NP NP NP ????
Redução polinomial de Problemas
Introdução à Teoria do NP-Completo
Sejam dois problemas de decisão D1 e D2 e sabe-se que existe um 
algoritmo A2 para solucionar D2. Suponhamos que se consiga 
transformar as entradas e saídas de D1 para as entradas e saídas 
de D2. Se essas transformações forem polinomiais, então diz-se 
que
D1 se reduz polinomialmente a D2 e pode-se transformar 
polinomialmente o algoritmo A2 para solucionar D1. A transforma-
ção polinommial é representada por D1 αααα D2.
Ex: Ciclo Hamiltoniano reduz-se, polinomialmente, a Caixeiro Viajante.
CH: Dado G, existe ciclo Hamiltoniano em G?
CV: Dado G´, completo, com arestas ponderadas, existe ciclo 
Hamiltoniano com peso total ≤ k?
Transformação de CH em CV:
A partir de G para CH, cria-se G´ completo para CV, com os 
seguintes pesos: para cada aresta (v,w) de G´, se ela existir em 
G, seu peso = 1; senão, seu peso = 2. k é feito = |V(G)|.
8
A Classe NPNPNPNP-Completo
Introdução à Teoria do NP-Completo
Define-se a seguinte subclasse de NP:
A Classe NPNPNPNP-Completo é formada pelos problemas de 
decisão D tais que:
a) D ∈∈∈∈ NP
b) Se D1 ∈∈∈∈ NP então D1 reduz-se polinomialmente a D.
Em 1971 Cook demonstrou o seguinte Teorema:
“Satisfatibilidade ∈∈∈∈ NPNPNPNP-Completo”.
A Classe NPNPNPNP-Completo
Introdução à Teoria do NP-Completo
A partir do Teorema de Cook, foram demonstrados que 
os seguintes problemas pertencem à classe NPNPNPNP-Completo:
E mais de 5000 problemas muito importantes, inclusive 
do ponto de vista comercial.
-Clique
-Conjunto independente
-Ciclo Hamiltoniano
-3-SAT
-Caixeiro Viajante
-Coloração de Vértices
-Cobertura de Vértices
-Mochila (Soma de Subconjuntos)
-Programação Inteira
A Classe NPNPNPNP-Completo
Introdução à Teoria do NP-Completo
Para provar que um problema D está na classe NP-
Completo, basta provar que um problema da classe 
reduz-se polinomialmente a D.
Prova: Faz-se a transformação de SAT para 3-SAT, criando-se 
E´ da seguinte forma:
Seja cada cláusula C de E, C = l1 | l2...| lk;
a) Se k = 1 ou 2, acrescentamos | l1 2 ou 1 vezes, respect. Se = 
3. mantemos a cláusula.
b) Caso contrário, criamos duas cláusulas C´e C´´, com
C´= l1 | l2 | Z, onde Z é nova variável e C´´= l3 | ...| lk | Z
Repetem-se os passos a) e b) até todas as cláusulas terem 3 
literais.
Teorema: 3-SAT ∈∈∈∈ NP-Completo
A Classe NPNPNPNP-Completo
Introdução à Teoria do NP-Completo
Prova (cont.):
Suponhamos E satisfatível. Para as literais comuns mantemos a 
mesma atribuição que satisfez E. As novas literais só aparecem em 
cláusulas oriundas de mais de 3 literais. Seja C uma dessas 
cláusulas, com C = C´ & C´´. Seja li a literal que satisfez C. Se i 
< 3, li satisfaz C´. Então basta fazer Z = F, que C´´ também é
satisfeita. Se i > 2, li satisfaz C´´. Basta, então, fazer Z = V, 
que C´ é satisfeita. Dessa forma, todas as cláusulas de E´ são 
também satisfeitas.
Suponhamos E´ satisfatível. Como os literais que satisfazem C´ e 
C´´ não podem ser Z e Z simultâneamente, existe algum literal li
que satisfaz a uma das duas cláusulas. Esse literal é usado para 
satisfazer C.
Logo E é satisfatível sse E´ é satisfatível. Como todas as 
transformações são polinomiais, SAT αααα 3-SAT e, portanto, 3-SAT 
pertence a NPNPNPNP-Completo.
Teorema: 3-SAT ∈∈∈∈ NP-Completo
A Classe NPNPNPNP-Completo
Introdução à Teoria do NP-Completo
Prova: Faz-se a transformação de SAT para Clique.
Seja E = C1 & C2 ...& Cn. Sejam x1, x1, x2,...xm os literais dessas 
cláusulas.
Constrói-se G da seguinte maneira:
G tem um vértice para cada literal (literal normal e sua negação). 
As arestas de G ligam os vértices v e w quando os literais 
correspondentes estiverem em cláusulas distintas e um deles não 
for a negação do outro. Para completar os dados de Clique, faz-se 
k = n. Ver exemplo, para E = (x1 | x2) & (x1 | x2 | x3) & (x3).
A construção é polinomial. Devemos mostrar que SAT tem resposta 
SIM sse Clique tem resposta SIM.
Se SAT responder SIM, todas as cláusulas são verdadeiras, i. e, 
existem n literais que assumem o valor V, sem haver a contradição 
de um literal e sua negação terem mesmo valor. Em G esses 
literais correspondem a vértices 2 a 2 adjacentes. Logo, vai haver 
uma Clique de tamanho k e a resposta de CLIQUE será SIM.
Teorema: Clique ∈∈∈∈ NP-Completo
A Classe NPNPNPNP-Completo
Introdução à Teoria do NP-Completo
Prova (cont.):
Reciprocamente, suponhamos que Clique responda Sim. Então G 
contém uma clique de tamanho k = n. Por construção, os vértices 
da clique correspondem a n literais de cláusulas distintas, sem 
nenhuma contradição. Isso quer dizer que cada cláusula é
satisfeita, o que torna E satisfeita. Logo, SAT também 
responderá SIM. Conclui-se que SAT αααα Clique e, portanto, Clique 
pertence a NPNPNPNP-Completo.
Teorema: Clique ∈∈∈∈ NP-Completo
x1
x1
x2x2
x3
x3
Grafo para
E = (x1 | x2) & 
(x1 | x2 | x3) & (x3).
9
Classes P P P P e NPNPNPNP COCOCOCO-NPNPNPNP e NPNPNPNP-Completo
Questões cruciais:
Introdução à Teoria do NP-Completo
P = P = P = P = NP NP NP NP ???? P = COP = COP = COP = CO----NP NP NP NP ∩∩∩∩ NP NP NP NP ? ? ? ? NP = CONP = CONP = CONP = CO----NP NP NP NP ????
(1.000.000 de dólares)
Se algum problema NPNPNPNP-Completo tiver um 
algoritmo polinomial ⇒⇒⇒⇒ todos os problemas de NPNPNPNP
são polinomiais ⇒⇒⇒⇒ PPPP = NPNPNPNP
Não há muitas esperanças de que isso ocorra, mas 
ninguém ainda provou.
Classes P P P P e NPNPNPNP COCOCOCO-NPNPNPNP e NPNPNPNP-Completo
Superando a NPNPNPNP-Completude:
Introdução à Teoria do NP-Completo
Heurísticas + Backtracking
Algoritmos Aproximativos
Algoritmos probabilísticos
Hierarquias de Classes de Problemas
...EXPEXPEXPEXPNPNPNPNP
PPPP
NPNPNPNP----CCCC
Problemas não classificados:
Número Composto
Isomorfismo de grafos
Introdução à Teoria do NP-Completo
FIM
Introdução à Teoria do NP-Completo