Upload
delacyr-ferreira
View
102
Download
3
Embed Size (px)
Citation preview
Análise de Algoritmos
As classes P eNP
Analise de Algoritmos – p. 1/21
Problemas de decisão e otimização
Problema de decisao: Existe uma solução quesatisfaz uma certa propriedade?Resposta: “sim” ou “não”.
Analise de Algoritmos – p. 2/21
Problemas de decisão e otimização
Problema de decisao: Existe uma solução quesatisfaz uma certa propriedade?Resposta: “sim” ou “não”.
Problema de otimizacao: Dentre as soluções quesatisfazem uma certa propriedade, qual é a melhorem relação à uma dada função.
Analise de Algoritmos – p. 2/21
Problemas de decisão e otimização
Exemplo: Problema do caixeiro viajante.
Otimização: determine um circuito hamiltonianode custo mínimo?
Analise de Algoritmos – p. 3/21
Problemas de decisão e otimização
Exemplo: Problema do caixeiro viajante.
Otimização: determine um circuito hamiltonianode custo mínimo?
Decisão: dado um valor L, existe um circuitohamiltoniano de custo ! L?
Analise de Algoritmos – p. 3/21
Problemas de decisão e otimização
Exemplo: Problema do caixeiro viajante.
Otimização: determine um circuito hamiltonianode custo mínimo?
Decisão: dado um valor L, existe um circuitohamiltoniano de custo ! L?
Outros exemplos: mochila, clique, etc.
Analise de Algoritmos – p. 3/21
As classes P e NP
O estudo da teoria da complexidade de algoritmosconcentra-se nos problemas de decisão.
Analise de Algoritmos – p. 4/21
As classes P e NP
O estudo da teoria da complexidade de algoritmosconcentra-se nos problemas de decisão.
Definicao: A classe P representa o conjunto dosproblemas de decisão que podem ser resolvidospor um algoritmo polinomial.
Analise de Algoritmos – p. 4/21
As classes P e NP
Definicao: A classe NP representa o conjunto dosproblemas de decisão em que dado qualquerinstância do problema para a qual a resposta é“sim”, existe um certificado validando este fato eque pode ser verificado em tempo polinomial.
Analise de Algoritmos – p. 5/21
As classes P e NP
Definicao: A classe NP representa o conjunto dosproblemas de decisão em que dado qualquerinstância do problema para a qual a resposta é“sim”, existe um certificado validando este fato eque pode ser verificado em tempo polinomial.
A partir destas definições, temos que
P " NP
Analise de Algoritmos – p. 5/21
As classes P e NP
Por exemplo:
Um dado grafo G
é bipartido?
Analise de Algoritmos – p. 6/21
As classes P e NP
Por exemplo:
Um dado grafo G
é bipartido?tem aresta de corte?
Analise de Algoritmos – p. 6/21
As classes P e NP
Por exemplo:
Um dado grafo G
é bipartido?tem aresta de corte?é hamiltoniano?
Analise de Algoritmos – p. 6/21
As classes P e NP
Por exemplo:
Um dado grafo G
é bipartido?tem aresta de corte?é hamiltoniano?é conexo?
Analise de Algoritmos – p. 6/21
As classes P e NP
Por exemplo:
Um dado grafo G
é bipartido?tem aresta de corte?é hamiltoniano?é conexo?tem uma clique de tamanho # k?
Analise de Algoritmos – p. 6/21
As classes P e NP
Por exemplo:
Um dado grafo G
é bipartido?tem aresta de corte?é hamiltoniano?é conexo?tem uma clique de tamanho # k?existe caminho de custo ! k entre osvértices u e v?
Analise de Algoritmos – p. 6/21
As classes P e NP
Por exemplo:
Dois grafos G e H são isomorfos?
Analise de Algoritmos – p. 7/21
As classes P e NP
Por exemplo:
Dois grafos G e H são isomorfos?
Uma fórmula boleana é satisfatível?
Analise de Algoritmos – p. 7/21
As classes P e NP
Por exemplo:
Dois grafos G e H são isomorfos?
Uma fórmula boleana é satisfatível?
Questão fundamental da teoria da computação:
P = NP?
Analise de Algoritmos – p. 7/21
As classes P e NP
Por exemplo:
Dois grafos G e H são isomorfos?
Uma fórmula boleana é satisfatível?
Questão fundamental da teoria da computação:
P = NP?
Em geral, acredita-se que a questão é falsa.
Analise de Algoritmos – p. 7/21
As classes P e NP
Como mostrar que a questão é falsa?
Analise de Algoritmos – p. 8/21
As classes P e NP
Como mostrar que a questão é falsa?Encontrar um problema em NP e mostrar quenenhum algoritmo polinomial pode resolvê-lo.
Analise de Algoritmos – p. 8/21
As classes P e NP
Como mostrar que a questão é falsa?Encontrar um problema em NP e mostrar quenenhum algoritmo polinomial pode resolvê-lo.
Como mostrar que a questão é verdadeira?
Analise de Algoritmos – p. 8/21
As classes P e NP
Como mostrar que a questão é falsa?Encontrar um problema em NP e mostrar quenenhum algoritmo polinomial pode resolvê-lo.
Como mostrar que a questão é verdadeira?Mostra que para todo problema em NP existealgoritmo polinomial que o resolve.
Analise de Algoritmos – p. 8/21
ExercíciosIndique quais dos problemas abaixo estão em NP.1. (MST) Dado um grafo G com custos inteiros nas
arestas, e um inteiro k, existe uma árvore geradora deG com custo máximo k?
2. (3-EXACT COVER) Dada uma famíliaF = {S1, S2, . . . , Sn} de n subconjuntos deS = {u1, u2, . . . , u3m}, com |Si| = 3, para todo 1 ! i ! n,existe uma subfamília de m subconjuntos que cobre S?
3. (MOCHILA 0$ 1) Dado inteiros cj , 1 ! j ! n, e k, existeum subconjunto S de {1, 2, . . . , n} tal que
!j!S cj = k?
4. (PARTIÇÃO) Dado inteiros c1, c2, . . . , cn, existe umsubconjunto S " {1, 2, . . . , n} tal que!
j!S cj =!
j /!S cj?
Analise de Algoritmos – p. 9/21
Redução entre problemas
Uma forma comum de resolver um dado problemaA é transformá-lo em um outro problema B cujasolução é conhecida e converter a solução de B
para uma solução de A. Este procedimento échamado de redução.
Analise de Algoritmos – p. 10/21
Redução entre problemas
Definicao de reducao: Dados dois problemas A e B.Uma redução polinomial de A para B (notaçãoA % B) é um algoritmo polinomial que resolve A
utilizando B, onde cada chamada de B é contadocomo um passo de computação.
Analise de Algoritmos – p. 11/21
Redução entre problemas
Definicao de reducao: Dados dois problemas A e B.Uma redução polinomial de A para B (notaçãoA % B) é um algoritmo polinomial que resolve A
utilizando B, onde cada chamada de B é contadocomo um passo de computação.
Exemplo: A seleção do k-ésimo mínimo pode serreduzido ao problema da ordenação.
Analise de Algoritmos – p. 11/21
Exemplo de redução
Problema 1: Sejam A = a1a2 . . . an e B = b1b2 . . . bnduas cadeias de caracteres. Determinar de B é umdeslocamento cíclico de A.
Analise de Algoritmos – p. 12/21
Exemplo de redução
Problema 1: Sejam A = a1a2 . . . an e B = b1b2 . . . bnduas cadeias de caracteres. Determinar de B é umdeslocamento cíclico de A.
OBS: B é deslocamento cíclico de A & B ésubcadeia de AA.
Analise de Algoritmos – p. 12/21
Exemplo de redução
Problema 1: Sejam A = a1a2 . . . an e B = b1b2 . . . bnduas cadeias de caracteres. Determinar de B é umdeslocamento cíclico de A.
OBS: B é deslocamento cíclico de A & B ésubcadeia de AA. Portanto, este problema podeser reduzido ao KMP .
Analise de Algoritmos – p. 12/21
Exemplo de redução
Problema 1: Sejam A = a1a2 . . . an e B = b1b2 . . . bnduas cadeias de caracteres. Determinar de B é umdeslocamento cíclico de A.
OBS: B é deslocamento cíclico de A & B ésubcadeia de AA. Portanto, este problema podeser reduzido ao KMP .
Problema 1 % KMP
Analise de Algoritmos – p. 12/21
Redução
Observações: Suponha que A % B.
Se B ' P então A ' P.
Analise de Algoritmos – p. 13/21
Redução
Observações: Suponha que A % B.
Se B ' P então A ' P.
Se B % C então A % C.
Analise de Algoritmos – p. 13/21
Redução
Observações: Suponha que A % B.
Se B ' P então A ' P.
Se B % C então A % C.
A % B significa que B é pelo menos tão difícilquanto A.
Analise de Algoritmos – p. 13/21
Problemas NP -completos
Definicao: Um problema de decisão A éNP-completo se
A ' NP e
B % A, para todo B ' NP .
Analise de Algoritmos – p. 14/21
Problemas NP -completos
Definicao: Um problema de decisão A éNP-completo se
A ' NP e
B % A, para todo B ' NP .
Propriedade: Seja A um problema NP-completo eB ' NP . Se A % B então B é NP-completo.
Analise de Algoritmos – p. 14/21
Problema da satisfatibilidade (SAT)
Dada uma expressão lógica (boleana) na formanormal conjuntiva, existe uma atribuição de valores(V ou F ) para suas variáveis tal que o resultado daexpressão seja verdadeiro?
S = (x+ y + z).(x+ y + z).(x + y + z)
Analise de Algoritmos – p. 15/21
Problema da satisfatibilidade (SAT)
S. A. Cook (1971) e L. A. Levin (1973) provaram,independentemente, que SAT é um problemaNP-completo.
Teorema [Cook – Levin]: SAT é NP-completo.
Analise de Algoritmos – p. 16/21
Problema 3-SAT
Dada uma expressão lógica na forma normalconjuntiva onde cada cláusula contém 3 variáveis,existe uma atribuição de valores (V ou F ) para asvariáveis tal que o resultado da expressão sejaverdadeiro?
S = (x+ y + z).(x+ y + z).(x + y + z)
Analise de Algoritmos – p. 17/21
Problema 3-SAT
Teorema: 3-SAT é NP-completo.
Analise de Algoritmos – p. 18/21
Problema 3-SAT
Teorema: 3-SAT é NP-completo.
Prova:
3-SAT ' NP (( )
Analise de Algoritmos – p. 18/21
Problema 3-SAT
Teorema: 3-SAT é NP-completo.
Prova:
3-SAT ' NP (( )
SAT % 3-SAT
Analise de Algoritmos – p. 18/21
Problema 3-SAT
Teorema: 3-SAT é NP-completo.
Prova:
3-SAT ' NP (( )
SAT % 3-SAT
Considere uma instância S do SAT. Vamosconstruir uma instância para 3-SAT da seguinteforma:
Analise de Algoritmos – p. 18/21
Problema 3-SAT
Seja C = (x1 + x2 + · · ·+ xk) uma cláusula do SAT.
Analise de Algoritmos – p. 19/21
Problema 3-SAT
Seja C = (x1 + x2 + · · ·+ xk) uma cláusula do SAT.
se k = 1 (C = (x1)), fazemos
C ) = (x1+y+z).(x1+y+z).(x1+y+z).(x1+y+z)
Analise de Algoritmos – p. 19/21
Problema 3-SAT
Seja C = (x1 + x2 + · · ·+ xk) uma cláusula do SAT.
se k = 1 (C = (x1)), fazemos
C ) = (x1+y+z).(x1+y+z).(x1+y+z).(x1+y+z)
se k = 2 (C = (x1 + x2)), fazemos
C ) = (x1 + x2 + z).(x1 + x2 + z)
Analise de Algoritmos – p. 19/21
Problema 3-SAT
Seja C = (x1 + x2 + · · ·+ xk) uma cláusula do SAT.
se k # 4, construímos
C ) = (x1 + x2 + y1).(x3 + y1 + y2).(x4 + y2 + y3)...
(xk$2 + yk$4 + yk$3).(yk$3 + xk$1 + xk)
Analise de Algoritmos – p. 20/21
Problema 3-SAT
Seja C = (x1 + x2 + · · ·+ xk) uma cláusula do SAT.
se k # 4, construímos
C ) = (x1 + x2 + y1).(x3 + y1 + y2).(x4 + y2 + y3)...
(xk$2 + yk$4 + yk$3).(yk$3 + xk$1 + xk)
Em cada caso, C é satisfatível& C ) é satisfatível.
Analise de Algoritmos – p. 20/21
Exercícios
1. Problema MAX-SAT: Dada uma expressãológica na forma normal conjuntiva, e um inteiroK, existe uma atribuição de valores para asvariáveis que satisfaz pelo menos K cláusulas?Mostre que MAX-SAT é NP-completo.
2. O que voce acha do problema 2-SAT? (Ele éNP-completo?)
Analise de Algoritmos – p. 21/21