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

  • View
    105

  • Download
    0

Embed Size (px)

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

  • Slide 1
  • maio/2000katia@cin.ufpe.br1 Introduo NP-completude Katia S. Guimares katia@cin.ufpe.br
  • Slide 2
  • maio/2000katia@cin.ufpe.br2 Problemas NP-Completos H muitos problemas com aplicaes prticas importantes para os quais no se conhece algoritmos polinomiais. Esse problemas so chamados intratveis. Dentre os problemas intratveis podemos citar muitas aplicaes inadiveis.
  • Slide 3
  • maio/2000katia@cin.ufpe.br3 Problemas NP-Completos Problemas Intratveis: - Gerenciamento de filas para uso de CPU (escalonamento) - Gerenciamento de memria (fragmentao) - rvore geradora de grau limitado (Proj. redes) - rvore geradora de dimetro limitado (Redes) - Caminho Hamiltoniano - Caixeiro Viajante (TSP) - Localizao de recursos em Sist. Distribudos.
  • Slide 4
  • maio/2000katia@cin.ufpe.br4 Problemas NP-Completos Informalmente, problemas intratveis so aqueles para os quais o melhor limite inferior conhecido polinomial, enquanto que o melhor algoritmo conhecido exponencial. exponencialpolinomial Problemas intratveis
  • Slide 5
  • maio/2000katia@cin.ufpe.br5 ABSTRAINDO O GRAU DO POLINMIO E A BASE DA FUNO EXPONENCIAL Antes, ns desejvamos nos abstrair das constantes aditivas e multiplicativas. Para expressarmos esta abstrao formalmente, introduzimos os conceitos de (f), (f) e (f). Como no sabemos se os problemas intratveis esto na classe dos polinomiais (n^c) ou dos exponenciais (c^n), vamos querer nos abstrair de qual seja o grau do polinmio ou a base da funo exponencial. Queremos saber somente a qual destas duas classes o problema pertence.
  • Slide 6
  • maio/2000katia@cin.ufpe.br6 Problemas de Deciso Para simplificar as definies, trataremos apenas de problemas de deciso, ou seja, problemas cuja soluo SIM ou NO. Ex: Entrada: G(V,E), x 1, x 2,..., x k V, C Sada: Existe em G um caminho passando por todos os vrtices x i dados, cujo custo seja no mximo C?
  • Slide 7
  • maio/2000katia@cin.ufpe.br7 Problemas de Deciso Se um problema P no de deciso (Ex: Qual o custo do menor caminho passando pelos vrtices dados?), ento existe um problema de deciso que ajudar a resolver o problema P em tempo igual ao tempo de resolver o problema de deciso correspondente, a menos de um fator polinomial.
  • Slide 8
  • maio/2000katia@cin.ufpe.br8 Problemas NP-completos Para podermos definir formalmente a classe NP-completo, vamos antes apresentar duas outras classes de problemas: - Classe NP - Classe NP-difcil NP-completo = NP NP-difcil
  • Slide 9
  • maio/2000katia@cin.ufpe.br9 Problemas NP NP uma classe de problemas para os quais existe um algoritmo polinomial, embora no determinstico (da o NP). (Note que esta classe inclui os problemas polinomiais.) Algoritmo NPpolinomial
  • Slide 10
  • maio/2000katia@cin.ufpe.br10 Algoritmos No-determinsticos Um algoritmo no-determinstico se ele escrito numa linguagem no-determinstica: - Contm todos os comandos de uma linguagem regular, e - Contm um comando salto-nd Os problemas com algoritmos polinomiais tambm pertencem classe NP, pois estes algoritmos usam uma linguagem no-determinstica, embora sem lanar mo do comando salto-nd.
  • Slide 11
  • maio/2000katia@cin.ufpe.br11 Algoritmos No-determinsticos Um algoritmo no-determinstico para um problema de deciso responde SIM se existe pelo menos uma maneira de fazer escolhas de execuo nos salto-nd de forma que a resposta do algoritmo seja SIM, e NO, caso todas as combinaes de escolhas de execuo nos salto-nd levem a uma resposta NO.
  • Slide 12
  • maio/2000katia@cin.ufpe.br12 Problema CLIQUE ENTRADA: - G(V, E), um grafo no-direcionado e sem peso nas arestas, e - k, um nmero natural, k |V| SADA: - Existe em G um subgrafo completo com k vrtices?
  • Slide 13
  • maio/2000katia@cin.ufpe.br13 Algoritmo NP para CLIQUE Algoritmo CLIQUE (G(V, E), k) Para cada v V faa /* Decidir se escolhido */ salto-nd { escolhido [v] true; escolhido [v] false } /* Vrtices escolhidos formam um clique? */ forma-clique true; Para cada v V faa se escolhido [v] ento /* v tem k-1 vizinhos marcados? */ cont 0; para todo w Adj(v) faa se escolhido [w] ento cont cont + 1; se cont k -1 ento forma-clique false; Output (forma-clique).
  • Slide 14
  • maio/2000katia@cin.ufpe.br14 Algoritmo NP para CLIQUE Custo do Algoritmo CLIQUE T(n) = [n] + [n + |E|] Note que - Se existir um clique no grafo G, ento existe uma seqncia de escolhas nos comandos salto-nd que levam a uma resposta SIM. - Se no existir um clique em G, a verificao ir forar o NO.
  • Slide 15
  • maio/2000katia@cin.ufpe.br15 Problemas NP-difceis A classe dos problemas NP-difceis contm os problemas de complexidade maior ou igual do problema SATisfatibilidade. Algoritmo NPpolinomial SATSAT
  • Slide 16
  • maio/2000katia@cin.ufpe.br16 Reduo Polinomial A maneira de mostrar que a complexidade de SAT um limite inferior para a com- plexidade de um problema P fazer uma reduo polinomial de SAT a este problema P, ou seja, definir uma soluo para SAT usando uma soluo para P como caixa preta.
  • Slide 17
  • maio/2000katia@cin.ufpe.br17 Reduo Polinomial Formalmente, reduo polinomial de um problema P* a um outro problema P, um algoritmo polinomial que transforma uma instncia x de P* em um instncia y de P, de forma que: P*(x) = SIM se e somente se P(y) =SIM.
  • Slide 18
  • maio/2000katia@cin.ufpe.br18 Reduo 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 tambm poder ser resolvido em tempo polinomial. Reduo Polinomial Algoritmo Polinomial para P Algoritmo polinomial para SAT y inst. de P x inst. de SAT x SAT y P (sse)
  • Slide 19
  • maio/2000katia@cin.ufpe.br19 Problema SAT Entrada: Expresso booleana, na Forma Normal Conjuntiva (FNC), ou seja, uma conjuno de disjunes. Sada: Existe uma valorao das variveis 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 )
  • Slide 20
  • maio/2000katia@cin.ufpe.br20 Reduo de SAT a Clique Algoritmo polinomial para, dada uma expresso booleana na FNC,, (instncia de SAT), gerar um grafo G(V,E) e um natural k |V| tal que: satisfatvel sse existe um k-clique em G. Algoritmo para gerar G(V,E) e k: Seja = c 1 c 2... c m V {v i j, onde i a clusula e j a varivel } E { (v i j, v k l ), onde i k e v i j v k l }.
  • Slide 21
  • maio/2000katia@cin.ufpe.br21 Reduo de SAT a Clique Exemplo: = ( x y z) ( x y z) ( y z) x y y z z z y x
  • Slide 22
  • maio/2000katia@cin.ufpe.br22 Reduo de SAT a Clique 1. O algoritmo de reduo polinomial. O nmero de vrtices gerados menor que o tamanho da entrada (nmero de smbolos na expresso booleana). O nmero de arestas geradas limitado superiormente por |V| x |V|.
  • Slide 23
  • maio/2000katia@cin.ufpe.br23 Reduo de SAT a Clique 2. satisfatvel sse existe um k-clique em G. Se satisfatvel, ento existe uma valora o das variveis em que faz verdadeira. Como est na FNC, h pelo menos um literal em cada clusula com valor verdadeiro. Considere os vrtices V de G que correspondem a estes literais. O subgrafo gerado G[V ] um m-clique.
  • Slide 24
  • maio/2000katia@cin.ufpe.br24 Reduo de SAT a Clique 2. satisfatvel sse existe um k-clique em G. Se existe um m-clique no grafo criado na reduo, ento, por construo de G, temos que: 1. Cada um dos vrtices deve corresponder a um literal de uma clusula diferente, e 2. As valoraes destes literais no podem se contradizer. possvel valorar as variveis corrresps a estes literais de forma a tornar verdadeira (as demais variveis podem tomar qualquer valor). Logo, satisfatvel.
  • Slide 25
  • maio/2000katia@cin.ufpe.br25 A Classe NP-Completo Como dissemos inicialmente, NP-completo = NP NP-difcil Algoritmo NPpolinomial SATSAT
  • Slide 26
  • maio/2000katia@cin.ufpe.br26 Classe NP-Completo - Abordagens H uma srie de tcnicas para lidar com problemas NP-completos. Dependendo da situao, algumas so mais adequadas do que outras. Ex. - Algoritmos de Aproximao - Programao Dinmica (Pseudo-polin.) - Algoritmos Randmicos
  • Slide 27
  • maio/2000katia@cin.ufpe.br27 Algoritmos de Aproximao Ex. Problema Bin-Packing Entrada: Nmeros 0 < x < 1 Sada: Quantos bins de capacidade 1 so necessrios para conter estes nmeros? Uma entrada poderia ser:.4.3.4.5.7.6.5.6 Abordagem 1: FIRST FIT
  • Slide 28
  • maio/2000katia@cin.ufpe.br28 Bin-Packing Entrada:.4.3.4.5.7.6.5.6 Abordagem 1: FIRST FIT Sada: {.4,.3}, {.4,.5}, {.7}, {.6}, {.5}, {.6} Garantia do FIRST FIT: de bins 2 timo. Abordagem 2: DECREASING FIRST FIT
  • Slide 29
  • maio/2000katia@cin.ufpe.br29 Bin-Packing Entrada:.4.3.4.5.7.6.5.6 Abordagem 2: DECREASING FIRST FIT Sada: {.7,.3}, {.6,.4}, {.6,.4}, {.5,.5} Garantia do DECREASING FIRST FIT: de bins 1.25 timo.
  • Slide 30
  • maio/2000katia@cin.ufpe.br30 Problema Soma dos Subconjuntos Entrada: n nmeros naturais Sada: Existe uma bipartio dos nmeros na entrada tal que as somas dos elementos em cada conjunto seja igual? Uma entrada poderia ser: 5 3 2 4 Abordagem: Programao Dinmica
  • Slide 31
  • maio/2000katia@cin.ufpe.br31 Problema Soma dos Subconjuntos Entrada: 5 3 2 4 Abordagem: Programao Dinmica 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