Introdução à NP-completude
Katia S. Guimarães
abril/2008
[email protected]
1
Problemas NP-Completos
Há muitos problemas com aplicações
práticas importantes para os quais não
se conhece algoritmos polinomiais.
Esse problemas são chamados intratáveis.
Dentre os problemas intratáveis podemos
citar muitas aplicações inadiáveis.
abril/2008
[email protected]
2
Problemas NP-Completos
Problemas Intratáveis:
- Gerenciamento de filas para uso de CPU
(escalonamento)
- Gerenciamento de memória (fragmentação)
- Árvore geradora de grau limitado (Proj. redes)
- Árvore geradora de diâmetro limitado (Redes)
- Caminho Hamiltoniano
- Caixeiro Viajante (TSP)
- Localização de recursos em Sist. Distribuídos.
abril/2008
[email protected]
3
Problemas NP-Completos
Informalmente, problemas intratáveis são
aqueles para os quais o melhor limite
inferior conhecido é polinomial, enquanto que
o melhor algoritmo conhecido é exponencial.
Problemas
intratáveis
polinomial
abril/2008
exponencial
[email protected]
4
ABSTRAINDO O GRAU DO POLINÔMIO
E A BASE DA FUNÇÃO EXPONENCIAL
Antes, nós desejávamos nos abstrair das
constantes aditivas e multiplicativas. Para
expressarmos esta abstração formalmente,
introduzimos os conceitos de (f), (f) e (f).
Como não sabemos se os problemas intratáveis
estão na classe dos polinomiais (n^c) ou dos
exponenciais (c^n), vamos querer nos abstrair
de qual seja o grau do polinômio ou a base da
função exponencial. Queremos saber somente
a qual destas duas classes o problema pertence.
abril/2008
[email protected]
5
Problemas de Decisão
Para simplificar as definições, trataremos
apenas de problemas de decisão, ou seja,
problemas cuja solução é “SIM” ou “NÃO”.
Ex:
Entrada: G(V,E), x1, x2, ..., xk V, C  
Saída: Existe em G um caminho passando
por todos os vértices xi dados,
cujo custo seja no máximo C?
abril/2008
[email protected]
6
Problemas de Decisão
Se um problema P não é de decisão
(Ex: Qual o custo do menor caminho
passando pelos vértices dados?),
então existe um problema de decisão
que ajudará a resolver o problema P
em tempo igual ao tempo de resolver o
problema de decisão correspondente,
a menos de um fator polinomial.
abril/2008
[email protected]
7
Problemas NP-completos
Para podermos definir formalmente a classe
NP-completo, vamos antes apresentar duas
outras classes de problemas:
- Classe NP
- Classe NP-difícil
NP-completo = NP  NP-difícil
abril/2008
[email protected]
8
Problemas NP
NP é uma classe de problemas para os
quais existe um algoritmo polinomial,
embora não determinístico (daí o NP).
(Note que esta classe inclui os problemas polinomiais.)
polinomial
abril/2008
Algoritmo NP
[email protected]
9
Algoritmos Não-determinísticos
Um algoritmo é não-determinístico se ele é
escrito numa linguagem não-determinística:
- Contém todos os comandos de uma
linguagem regular, e
- Contém um comando salto-nd
Os problemas com algoritmos polinomiais também
pertencem à classe NP, pois estes algoritmos
usam uma linguagem não-determinística, embora
sem lançar mão do comando salto-nd.
abril/2008
[email protected]
10
Algoritmos Não-determinísticos
Um algoritmo não-determinístico para um
problema de decisão responde
“SIM” se existe pelo menos uma maneira
de fazer escolhas de execução nos
salto-nd de forma que a resposta
do algoritmo seja “SIM”, e
“NÃO”, caso todas as combinações de
escolhas de execução nos salto-nd
levem a uma resposta “NÃO”.
abril/2008
[email protected]
11
Problema CLIQUE
ENTRADA:
- G(V, E), um grafo não-direcionado e sem
peso nas arestas, e
- k , um número natural, k  |V|
SAÍDA:
- Existe em G um subgrafo completo com
k vértices?
abril/2008
[email protected]
12
Algoritmo NP para CLIQUE
Algoritmo CLIQUE (G(V, E), k)
Para cada v  V faça
/* Decidir se escolhido */
salto-nd
{ escolhido [v]  true;
escolhido [v]  false }
/* Vértices escolhidos formam um clique? */
forma-clique  true;
Para cada v  V faça
se escolhido [v] então
/* v tem k-1 vizinhos marcados? */
cont  0;
para todo w  Adj(v) faça
se escolhido [w] então cont  cont + 1;
se cont  k -1 então forma-clique  false;
Output (forma-clique).
abril/2008
[email protected]
13
Algoritmo NP para CLIQUE
Custo do Algoritmo CLIQUE
T(n) = [n] + [n + |E|]
Note que
- Se existir um clique no grafo G,
então existe uma seqüência de
escolhas nos comandos salto-nd
que levam a uma resposta “SIM”.
- Se não existir um clique em G,
a verificação irá forçar o “NÃO”.
abril/2008
[email protected]
14
Problemas NP-difíceis
A classe dos problemas NP-difíceis contém
os problemas de complexidade maior ou
igual à do problema SATisfatibilidade.
S
A
T
polinomial
abril/2008
Algoritmo NP
[email protected]
15
Redução Polinomial
A maneira de mostrar que a complexidade
de SAT é um limite inferior para a complexidade de um problema P é fazer uma
redução polinomial de SAT a este problema
P, ou seja, definir uma solução para SAT
usando uma solução para P como “caixa
preta”.
abril/2008
[email protected]
16
Redução Polinomial
Formalmente, redução polinomial de um
problema P* a um outro problema P, é um
algoritmo polinomial que transforma uma
instância x de P* em um instância y de P,
de forma que:
P*(x) = “SIM” se e somente se P(y) =“SIM”.
abril/2008
[email protected]
17
Redução Polinomial
A complexidade de SAT é um limite inferior
para a complexidade do problema P
porque se o problema P for resolvido em
tempo polinomial, o problema SAT também
poderá ser resolvido em tempo polinomial.
x inst. de SAT
Redução
Polinomial
y inst. de P
Algoritmo
Polinomial
para P
x  SAT
(sse)
yP
Algoritmo polinomial para SAT
abril/2008
[email protected]
18
Problema SAT
Entrada:
Expressão booleana , na Forma Normal Conjuntiva
(FNC), ou seja, uma conjunção de disjunções.
Saída:
Existe uma valoração das variáveis de  de forma
que  seja verdadeira?
Ex:  = (x  y  z)  (x  y  z)  (x  y  z)
A resposta para  é “SIM”
abril/2008
[email protected]
( x=1, y=1, z=0 )
19
Redução de SAT a Clique
Algoritmo polinomial para, dada uma expressão
booleana na FNC, , (instância de SAT), gerar
um grafo G(V,E) e um natural k  |V| tal que:
 é satisfatível sse existe um k-clique em G.
Algoritmo para gerar G(V,E) e k:
Seja  = c1  c2  ...  cm
V  {vi j, onde i é a cláusula e j é a variável }
E  { (vi j, v k l), onde i  k e
vi j  v k l }.
abril/2008
[email protected]
20
Redução de SAT a Clique
Exemplo:
 = ( x  y  z)  (x  y  z)  (y  z)
x
x
y
y
y
z
z
abril/2008
z
[email protected]
21
Redução de SAT a Clique
1. O algoritmo de redução é polinomial.
O número de vértices gerados é menor
que o tamanho da entrada (número de
símbolos na expressão booleana).
O número de arestas geradas é limitado
superiormente por |V| x |V|.
abril/2008
[email protected]
22
Redução de SAT a Clique
2.  é satisfatível sse existe um k-clique em G.
 Se  é satisfatível, então existe uma valora
ção das variáveis em  que faz  verdadeira.
Como  está na FNC, há pelo menos um
literal em cada cláusula com valor verdadeiro.
Considere os vértices V de G que correspondem
a estes literais. O subgrafo gerado G[V] é um
m-clique.
abril/2008
[email protected]
23
Redução de SAT a Clique
2.  é satisfatível sse existe um k-clique em G.
 Se existe um m-clique no grafo criado na redução,
então, por construção de G, temos que:
1. Cada um dos vértices deve corresponder a
um literal de uma cláusula diferente, e
2. As valorações destes literais não podem se
contradizer.
É possível valorar as variáveis corrresps a estes
literais de forma a tornar  verdadeira
(as demais variáveis podem tomar qualquer valor).
Logo,  é satisfatível.
abril/2008
[email protected]
24
A Classe NP-Completo
Como dissemos inicialmente,
NP-completo = NP  NP-difícil
S
A
T
polinomial
abril/2008
Algoritmo NP
[email protected]
25
Classe NP-Completo - Abordagens
Há uma série de técnicas para lidar com
problemas NP-completos. Dependendo da
situação, algumas são mais adequadas do
que outras.
Ex.
- Algoritmos de Aproximação
- Programação Dinâmica (Pseudo-polin.)
- Algoritmos Randômicos
abril/2008
[email protected]
26
Algoritmos de Aproximação
Ex. Problema Bin-Packing
Entrada: Números 0 < x < 1
Saída: Quantos bins de capacidade 1 são
necessários para conter estes números?
Uma entrada poderia ser:
.4 .3 .4 .5 .7 .6 .5 .6
Abordagem 1: FIRST FIT
abril/2008
[email protected]
27
Bin-Packing
Entrada: .4 .3 .4 .5 .7 .6 .5 .6
Abordagem 1: FIRST FIT
Saída: {.4, .3}, { .4, .5}, {.7}, {.6}, {.5}, {.6}
Garantia do FIRST FIT:
 de bins  2  ótimo.
Abordagem 2: DECREASING FIRST FIT
abril/2008
[email protected]
28
Bin-Packing
Entrada: .4 .3 .4 .5 .7 .6 .5 .6
Abordagem 2: DECREASING FIRST FIT
Saída: {.7, .3}, {.6, .4}, { .6, .4}, {.5, .5}
Garantia do DECREASING FIRST FIT:
 de bins  1.25  ótimo.
abril/2008
[email protected]
29
Problema Soma dos Subconjuntos
Entrada: n números naturais
Saída: Existe uma bipartição dos números
na entrada tal que as somas dos elementos
em cada conjunto seja igual?
Uma entrada poderia ser:
5 3 2 4
Abordagem: Programação Dinâmica
abril/2008
[email protected]
30
Problema Soma dos Subconjuntos
Entrada: 5 3 2
4
Abordagem: Programação Dinâmica
5
3
2
4
0
0
0
0
0
0
x
x
0
x
x
x
0
0
0
x
x
x
x
x
0
0
0
x
0
0
x
x
0
x
x
x
0
0
0
x
0
0
x
x
0 0 0
0 0 0
0 0 0
x x 0
0
0
0
x
Saída: Matriz [n,  xi / 2]
Custo: Tamanho da matriz = n   xi
(Pseudo-Polinomial)
abril/2008
[email protected]
31
Problema Soma dos Subconjuntos
Entrada: 7 3 2
4
Abordagem: Programação Dinâmica
7
3
2
4
1 2
3 4
5 6
7
0
0
0
0
0
x
x
x
0
0
x
x
x
x
x
x
0
0
x
x
0
0
0
x
0
0
0
x
8 9 10 11 12 13 14 15 16
0
0
0
0
0
0
x
x
0
x
x
x
0
0
0
x
0
0
x
x
0
0
0
x
0
0
0
x
0
0
0
0
0
0
0
x
Saída: Matriz [4, 8]
abril/2008
[email protected]
32
Algoritmo de Programação Dinâmica
para Soma dos Subconjuntos
soma  0
para i = 1 .. n faça
soma  soma + A [i]
para j = 0 .. soma faça
Matriz [1, j]  0
Matriz [1, A[1] ]  1
para i = 2 .. n faça
para j = 1 .. soma faça
Matriz [i, j]  Matriz [i-1, j] /* Copia linha anterior */
se A[i] < j então Matriz [i-1, j-A[i] ]  1
Matriz [i, A[i] ]  1
devolva ( Matriz [n, soma/2] )
abril/2008
[email protected]
33