Estudos sobre PROBLEMAS P-NP-NP-COMPLETO.pptx

Problemas P, NP e NP-Completos

1. P r o b l e m a s P , N P e N P C Melhor solução comprovada demanda complexidade pelo menos exponencial Problemas Não Tratáveis (NT) Todos os problemas computáveis NP NT P Melhor solução demanda complexidade até polinomial Problemas Polinomiais (P) Melhor solução encontrada é de ordem exponencial, mas não se sabe se é, de fato, a melhor solução possível Problemas Não-deterministicamente Polinomiais (NP) NP C Problemas NP tais que todos os outros são redutíveis a eles em tempo polinomial Problemas NP-Completo (NPC) N P N P N P N P 1

2. P r o b l e m a s P , N P e N P C Exemplo: S u p o nh a q u e d e s e j e m o s s a b er s e e x i s t e u m d e t e r m in a d o número em uma lista ordenada de valores. Qual a complexidade desse problema? Problemas polinomiais (P): aqueles cuja melhor solução demanda algoritmos com complexidade (assintótica) de ordem até polinomial O( n c ) 13 L i s t a 1 3 5 6 7 9 10 12 15 Solução trivial: O( n ) É a melhor solução? Busca binária: O(log 2 n ) Ela contém o número 8?

3. P r o b l e m a s P , N P e N P C Problema do Caixeiro Viajante: Dado um mapa com n cidades e a distância entre cada par de cidades, é possível obter um percurso para um vendedor de modo que ele o complete dentro de uma dada quilometragem, visitando cada cidade uma única vez e retornando ao ponto de partida? J ag u a r i ún a Qual é a rota de menor custo? 14 Ca mp i n as Hortolândia Itat i b a nós ( n -1)! 4 6 10 362880 Qual é a ordem de complexidade? Exponencial: O( c n ) É a melhor solução encontrada? Nunca se comprovou! Problema Não-deterministicamente Polinomial (NP) 1 5 km J J J J J J C C H H I I Rotas H I I C C H I H C I H C J J J J J J Custo 93 90 90 93 93 93 A s o lu ç ão é o b t id a a n a li s a n d o - s e a s ( n - 1 ) ! p o s s i b il i d a d e s .

4. Complexidade Para acharmos o número  R( n )  de rotas para o caso de  n  cidades, basta fazer um raciocínio combinatório simples e clássico. Dado n = 4 cidades, a primeira e última posição são fixas, de modo que elas não afetam o cálculo; na segunda posição podemos colocar qualquer uma das 3 cidades restantes B, C e D, e uma vez escolhida uma delas, podemos colocar qualquer uma das 2 restantes na terceira posição; na quarta posição não teríamos nenhuma escolha, pois sobrou apenas uma cidade; consequentemente, o número de rotas é 3 x 2 x 1 = 6. De modo semelhante, para o caso de n cidades, como a primeira é fixa, é (n-1) x (n-2) x ... x 2 x 1. De modo que, usando a notação de fatorial:  R( n ) = ( n - 1 )! .

5. P r o b l e m a s P , N P e N P C Problemas não-deterministicamente polinomiais (NP): aqueles cuja melhor solução conhecida demanda algoritmos com complexidade (assintótica) de ordem exponencial Ο( c n ). Contudo, ainda não se sabe se esta é, de fato, a melhor solução que pode ser alcançada. Se for provado que um algoritmo de ordem O( c n ) representa a melhor solução possível para o problema, dizemos que estamos diante de um problema não-tratável . Problemas tratáveis: aqueles cuja solução demanda um algoritmo de ordem polinomial ou menor E aqueles que ainda não se provou que a melhor solução demanda algoritmos de ordem exponencial ou maior. Problemas não-tratáveis: já se comprovou que a melhor solução possível demanda um algoritmo de ordem exponencial ou ainda mais custoso. 5

6. P r o b l e m a s P , N P e N P C Problema da Torre de Hanoi: Dado um conjunto de n discos dispostos em ordem decrescente de tamanho, o objetivo é mover a pilha para outro pino usando um terceiro como auxiliar. Restrições: Somente um disco pode ser movido a cada instante. Cada movimento consiste em retirar o disco do topo de uma pilha e movê- lo ao topo de outra pilha. Nenhum disco pode ser colocado sobre outro que seja menor do que ele. 6

7. P r o b l e m a s P , N P e N P C Problema da Torre de Hanoi: Exemplo: 3 discos I ní c i o 4 Caso geral: o número mínimo de movimentos é igual a 2³-1=8-1 generalizando 2 n – 1. O( 2 n ) 17 1 2 3 5 6 7

8. P r o b l e m a s P , N P e N P C Questão: Será que os problemas pertencentes à classe NP são, na verdade, problemas P para os quais ainda não conseguimos descobrir algoritmos que nos deem uma solução em tempo polinomial? Em outras palavras, P = NP? Esta questão é um dos maiores desafios não resolvidos da ciência da computação – um dos sete problemas valendo 1 milhão de dólares ( Millenium Prize Problems, Clay Mathematics Institute). Alguns problemas NP, contudo, são de especial importância e podem ser úteis na tentativa de solucionar esta questão. 18

9. P r o b l e m a s P , N P e N P C Problema da mochila ( knapsack ): é um problema de otimização combinatória. O objetivo é que se preencha uma mochila com um conjunto de itens tal que se atinja o maior valor total, não ultrapassando o peso máximo suportado. 19 Problema cuja melhor solução conhecida demanda um algoritmo de ordem exponencial Problema NP É interessante observar que diversos outros problemas se reduzem ao problema da mochila Investimento de capitais Corte e empacotamento - Orçamento - Criptografia de chave pública Desta forma, se encontrarmos uma solução em tempo polinomial para o problema da mochila, teremos uma solução O( n c ) para todos os outros problemas da mesma classe. O problema da Mochila é NP-Completo

10. P r o b l e m a s P , N P e N P C Problemas NP-Completos (NPC): subconjunto de NP formado por certos problemas tais que todos os demais problemas em NP são redutíveis a eles em tempo polinomial. Os problemas NPC podem ser muito úteis na investigação da questão P = NP. Caso seja provado que P = NP, então inúmeros problemas para os quais hoje só se vislumbram algoritmos exponenciais ou ainda de maior complexidade, na verdade, têm solução de menor complexidade (P). Caso seja demonstrado que P ≠ NP, então não há razão para buscar estes algoritmos. Ponto importante: obter um algoritmo eficiente (polinomial) para qualquer problema NPC implicará que um algoritmo eficiente (polinomial) terá sido obtido para toda esta classe de problemas (NPC). E, consequentemente, para NP. Com isto terá sido provado que P = NPC e, equivalentemente, que P=NP. 10

11. P r o b l e m a s P , N P e N P C Mas o que significa dizer que um problema é redutível a outro? Redução é a transformação de um problema em outro. Por exemplo, um problema de decisão Y é redutível a um problema de decisão X se existe um algoritmo que transforma qualquer instância y1 de Y em uma instância x1 de X , tal que y1 é verdadeira se e somente se x1 for verdadeira. Informalmente, Y é redutível a X se Y for um subproblema ou caso particular de X . Se um problema Y pode ser reduzido a X , uma solução para X oferece uma solução para Y . Deste modo, resolver Y não pode ser mais custoso do que resolver X (ou seja, não pode exigir tempo maior). 11

12. P r o b l e m a s P , N P e N P C Mas o que significa dizer que um problema é redutível a outro? Exemplo: o problema do quadrado-perfeito ( Y ) é polinomialmente redutível ao problema de equação de 2º grau inteira ( X ). Quadrado perfeito: dada uma entrada n , número natural, é preciso decidir se existe um natural j tal que j 2 = n . Equação de 2º grau inteira: dada uma entrada composta pelos inteiros a , b e c , é preciso decidir se existe um inteiro x tal que ax 2 + bx + c = 0. Escolhendo a = 1, b = 0 e c = - n , ao resolver o problema de equação de 2º grau, teremos resolvido o problema do quadrado perfeito. 12