Transcript
Page 1: Maio/2000katia@cin.ufpe.br1 Introdução à NP-completude Katia S. Guimarães katia@cin.ufpe.br

maio/2000 [email protected] 1

Introdução à NP-completude

Katia S. Guimarã[email protected]

Page 2: Maio/2000katia@cin.ufpe.br1 Introdução à NP-completude Katia S. Guimarães katia@cin.ufpe.br

maio/2000 [email protected] 2

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.

Page 3: Maio/2000katia@cin.ufpe.br1 Introdução à NP-completude Katia S. Guimarães katia@cin.ufpe.br

maio/2000 [email protected] 3

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.

Page 4: Maio/2000katia@cin.ufpe.br1 Introdução à NP-completude Katia S. Guimarães katia@cin.ufpe.br

maio/2000 [email protected] 4

Problemas NP-Completos

Informalmente, problemas intratáveis são aqueles para os quais o melhor limite inferior conhecido é polinomial, enquanto queo melhor algoritmo conhecido é exponencial.

exponencialpolinomial

Problemas intratáveis

Page 5: Maio/2000katia@cin.ufpe.br1 Introdução à NP-completude Katia S. Guimarães katia@cin.ufpe.br

maio/2000 [email protected] 5

ABSTRAINDO O GRAU DO POLINÔMIOE 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áveisestão na classe dos polinomiais (n^c) ou dos exponenciais (c^n), vamos querer nos abstrairde 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.

Page 6: Maio/2000katia@cin.ufpe.br1 Introdução à NP-completude Katia S. Guimarães katia@cin.ufpe.br

maio/2000 [email protected] 6

Problemas de Decisão

Para simplificar as definições, trataremosapenas 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?

Page 7: Maio/2000katia@cin.ufpe.br1 Introdução à NP-completude Katia S. Guimarães katia@cin.ufpe.br

maio/2000 [email protected] 7

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ãoque 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.

Page 8: Maio/2000katia@cin.ufpe.br1 Introdução à NP-completude Katia S. Guimarães katia@cin.ufpe.br

maio/2000 [email protected] 8

Problemas NP-completos

Para podermos definir formalmente a classeNP-completo, vamos antes apresentar duas outras classes de problemas:

- Classe NP - Classe NP-difícil

NP-completo = NP NP-difícil

Page 9: Maio/2000katia@cin.ufpe.br1 Introdução à NP-completude Katia S. Guimarães katia@cin.ufpe.br

maio/2000 [email protected] 9

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.)

Algoritmo NPpolinomial

Page 10: Maio/2000katia@cin.ufpe.br1 Introdução à NP-completude Katia S. Guimarães katia@cin.ufpe.br

maio/2000 [email protected] 10

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émpertencem à classe NP, pois estes algoritmos usam uma linguagem não-determinística, embora sem lançar mão do comando salto-nd.

Page 11: Maio/2000katia@cin.ufpe.br1 Introdução à NP-completude Katia S. Guimarães katia@cin.ufpe.br

maio/2000 [email protected] 11

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”.

Page 12: Maio/2000katia@cin.ufpe.br1 Introdução à NP-completude Katia S. Guimarães katia@cin.ufpe.br

maio/2000 [email protected] 12

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?

Page 13: Maio/2000katia@cin.ufpe.br1 Introdução à NP-completude Katia S. Guimarães katia@cin.ufpe.br

maio/2000 [email protected] 13

Algoritmo NP para CLIQUEAlgoritmo 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).

Page 14: Maio/2000katia@cin.ufpe.br1 Introdução à NP-completude Katia S. Guimarães katia@cin.ufpe.br

maio/2000 [email protected] 14

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”.

Page 15: Maio/2000katia@cin.ufpe.br1 Introdução à NP-completude Katia S. Guimarães katia@cin.ufpe.br

maio/2000 [email protected] 15

Problemas NP-difíceis

A classe dos problemas NP-difíceis contémos problemas de complexidade maior ouigual à do problema SATisfatibilidade.

Algoritmo NPpolinomial

SAT

Page 16: Maio/2000katia@cin.ufpe.br1 Introdução à NP-completude Katia S. Guimarães katia@cin.ufpe.br

maio/2000 [email protected] 16

Redução Polinomial

A maneira de mostrar que a complexidade de SAT é um limite inferior para a com- plexidade 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”.

Page 17: Maio/2000katia@cin.ufpe.br1 Introdução à NP-completude Katia S. Guimarães katia@cin.ufpe.br

maio/2000 [email protected] 17

Redução Polinomial

Formalmente, redução polinomial de um problema P* a um outro problema P, é umalgoritmo 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”.

Page 18: Maio/2000katia@cin.ufpe.br1 Introdução à NP-completude Katia S. Guimarães katia@cin.ufpe.br

maio/2000 [email protected] 18

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.

ReduçãoPolinomial

AlgoritmoPolinomial

para P

Algoritmo polinomial para SAT

y inst. de Px inst. de SATx SAT

y P

(sse)

Page 19: Maio/2000katia@cin.ufpe.br1 Introdução à NP-completude Katia S. Guimarães katia@cin.ufpe.br

maio/2000 [email protected] 19

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” ( x=1, y=1, z=0 )

Page 20: Maio/2000katia@cin.ufpe.br1 Introdução à NP-completude Katia S. Guimarães katia@cin.ufpe.br

maio/2000 [email protected] 20

Redução de SAT a Clique

Algoritmo polinomial para, dada uma expressãobooleana na FNC, , (instância de SAT), gerarum 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 }.

Page 21: Maio/2000katia@cin.ufpe.br1 Introdução à NP-completude Katia S. Guimarães katia@cin.ufpe.br

maio/2000 [email protected] 21

Redução de SAT a Clique

Exemplo: = ( x y z) (x y z) (y z)

x

y

y

z

z

z

y

x

Page 22: Maio/2000katia@cin.ufpe.br1 Introdução à NP-completude Katia S. Guimarães katia@cin.ufpe.br

maio/2000 [email protected] 22

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 é limitadosuperiormente por |V| x |V|.

Page 23: Maio/2000katia@cin.ufpe.br1 Introdução à NP-completude Katia S. Guimarães katia@cin.ufpe.br

maio/2000 [email protected] 23

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 umliteral em cada cláusula com valor verdadeiro.

Considere os vértices V de G que correspondem a estes literais. O subgrafo gerado G[V] é umm-clique.

Page 24: Maio/2000katia@cin.ufpe.br1 Introdução à NP-completude Katia S. Guimarães katia@cin.ufpe.br

maio/2000 [email protected] 24

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, e2. As valorações destes literais não podem se contradizer.É possível valorar as variáveis corrresps a estesliterais de forma a tornar verdadeira (as demais variáveis podem tomar qualquer valor). Logo, é satisfatível.

Page 25: Maio/2000katia@cin.ufpe.br1 Introdução à NP-completude Katia S. Guimarães katia@cin.ufpe.br

maio/2000 [email protected] 25

A Classe NP-Completo

Como dissemos inicialmente,

NP-completo = NP NP-difícil

Algoritmo NPpolinomial

SAT

Page 26: Maio/2000katia@cin.ufpe.br1 Introdução à NP-completude Katia S. Guimarães katia@cin.ufpe.br

maio/2000 [email protected] 26

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

Page 27: Maio/2000katia@cin.ufpe.br1 Introdução à NP-completude Katia S. Guimarães katia@cin.ufpe.br

maio/2000 [email protected] 27

Algoritmos de Aproximação

Ex. Problema Bin-Packing

Entrada: Números 0 < x < 1Saí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

Page 28: Maio/2000katia@cin.ufpe.br1 Introdução à NP-completude Katia S. Guimarães katia@cin.ufpe.br

maio/2000 [email protected] 28

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

Page 29: Maio/2000katia@cin.ufpe.br1 Introdução à NP-completude Katia S. Guimarães katia@cin.ufpe.br

maio/2000 [email protected] 29

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.

Page 30: Maio/2000katia@cin.ufpe.br1 Introdução à NP-completude Katia S. Guimarães katia@cin.ufpe.br

maio/2000 [email protected] 30

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 4Abordagem: Programação Dinâmica

Page 31: Maio/2000katia@cin.ufpe.br1 Introdução à NP-completude Katia S. Guimarães katia@cin.ufpe.br

maio/2000 [email protected] 31

Problema Soma dos Subconjuntos

Entrada: 5 3 2 4Abordagem: Programação Dinâmica

5 0 0 0 0 x 0 0 0 0 0 0 0 0

0 3 0 0 x 0 x 0 0 x 0 0 0 0 0 0 2 0 x x 0 x 0 x x 0 x 0 0 0 0 4 0 x x x x x x x 0 x x x 0 x

Saída: Matriz [n, xi / 2]

Custo: Tamanho da matriz = n xi

(Pseudo-Polinomial)