Teoria da Computacao - Lista de Exercicios sobre Classes P e NP

Atividade 7 Teoria da Computação 7a Etapa do Curso de Ciência da Computação FCI Mackenzie 1 Fazer um diagrama explicitando a localização do teste de primalidade em termos das classes P e NP 2 Por que P está necessariamente incluído em NP 3 Um subconjunto I de nós de G é um conjunto independente também conhecido como anticlique se nenhum par de nós de I está conectado por um arco de G Um subconjunto independente é máximo se ele for o maior subconjunto independente de nós deste grafo Por exemplo no grafo abaixo um grafo de Petersen generalizado os 9 nós acinzentados formam o máximo conjunto independente de nós do grafo Sabese que a determinação do máximo conjunto independente de um grafo qualquer é um problema NP Completo Supondo que se conseguiu provar que não existe um algoritmo de tempo polinomial para o problema isso tem alguma consequência a respeito do problema P vs NP 4 Conforme definimos um problema B é NPHard ou NPDifícil se todo problema A NP é redutível polinomialmente a B Por exemplo sabese que o TSP Travelling Salesman Problem Problema do Caixeiro Viajante é NPHard Supondo que se conseguiu provar a inexistência de um algoritmo de tempo polinomial para o problema isso tem alguma consequência a respeito do problema P vs NP 5 O que representa a classe NC de complexidade e qual o seu relacionamento com a classe P O que representa a classe de complexidade Pcomplete Pcompleto Atividade 7 Teoria da Computação 7a Etapa do Curso de Ciência da Computação FCI Mackenzie 1 Fazer um diagrama explicitando a localização do teste de primalidade em termos das classes P e NP Podemos localizar o teste de primalidade em termos das classes P e NP da seguinte maneira O problema da primalidade pertence a NP uma vez que um possível certificado da primalidade de um número é uma lista dos fatores primos do número e este certificado pode ser verificado em tempo polinomial Não se sabe se o problema da primalidade pertence a P ou é NPcompleto No entanto existe um algoritmo determinístico polinomialmente limitado conhecido como teste de primalidade de AKS que pode testar se um número é primo em tempo polinomial Isso sugere que o problema da primalidade pode estar em P No entanto o teste de primalidade de AKS tem uma complexidade assintótica muito alta o que o torna impraticável para a maioria dos tamanhos de entrada Dessa forma o problema da primalidade está em NP mas ainda não se sabe se ele está em P O teste de primalidade de AKS é um algoritmo determinístico polinomialmente limitado que sugere que o problema da primalidade pode estar em P mas não está claro se existem outros algoritmos mais eficientes que possam resolver o problema de forma determinística em tempo polinomial 2 Por que P está necessariamente incluído em NP P está necessariamente incluído em NP porque todos os problemas em P também estão em NP Em outras palavras se um problema pode ser resolvido em tempo polinomial determinístico então ele pode ser resolvido em tempo polinomial não determinístico Isso ocorre porque um algoritmo não determinístico pode adivinhar a resposta certa para um problema em tempo polinomial e depois verificar se essa resposta é correta em tempo polinomial Como qualquer problema que pode ser resolvido em tempo polinomial determinístico também pode ser resolvido em tempo polinomial não determinístico todos os problemas em P também estão em NP Para dar um exemplo considere o problema da ordenação É bem conhecido que a ordenação pode ser resolvida em tempo polinomial determinístico usando algoritmos como o merge sort e o quicksort No entanto também é possível resolver o problema da ordenação em tempo polinomial não determinístico Basta adivinhar uma permutação aleatória dos elementos da lista e verificar em tempo polinomial se a permutação está ordenada corretamente Como resultado o problema da ordenação está em P e também está em NP 3 Um subconjunto I de nós de G é um conjunto independente também conhecido como anticlique se nenhum par de nós de I está conectado por um arco de G Um subconjunto independente é máximo se ele for o maior subconjunto independente de nós deste grafo Por exemplo no grafo abaixo um grafo de Petersen generalizado os 9 nós acinzentados formam o máximo conjunto independente de nós do grafo Sabese que a determinação do máximo conjunto independente de um grafo qualquer é um problema NP Completo Supondo que se conseguiu provar que não existe um algoritmo de tempo polinomial para o problema isso tem alguma consequência a respeito do problema P vs NP Sim a prova da inexistência de um algoritmo de tempo polinomial para o problema de determinar o máximo conjunto independente de um grafo teria importantes consequências em relação ao problema P vs NP Em primeiro lugar é importante notar que a determinação do máximo conjunto independente é um problema NPcompleto o que significa que é improvável que exista um algoritmo eficiente para resolvêlo em todos os casos No entanto a prova da inexistência de um algoritmo de tempo polinomial para esse problema seria uma evidência significativa de que P NP Isso ocorre porque se houvesse um algoritmo de tempo polinomial para determinar o máximo conjunto independente de um grafo então haveria um algoritmo de tempo polinomial para todos os problemas em NP já que a determinação do máximo conjunto independente é NPcompleto Portanto a inexistência de um algoritmo de tempo polinomial para determinar o máximo conjunto independente de um grafo sugere que não há um algoritmo de tempo polinomial para nenhum problema NPcompleto o que por sua vez sugere que P NP Em resumo a prova da inexistência de um algoritmo de tempo polinomial para determinar o máximo conjunto independente de um grafo seria uma evidência significativa de que P NP embora não seja uma prova conclusiva 4 Conforme definimos um problema B é NPHard ou NPDifícil se todo problema A NP é redutível polinomialmente a B Por exemplo sabese que o TSP Travelling Salesman Problem Problema do Caixeiro Viajante é NPHard Supondo que se conseguiu provar a inexistência de um algoritmo de tempo polinomial para o problema isso tem alguma consequência a respeito do problema P vs NP Sim a prova da inexistência de um algoritmo de tempo polinomial para o problema TSP que é NPhard teria importantes consequências em relação ao problema P vs NP Em primeiro lugar a prova da inexistência de um algoritmo de tempo polinomial para o TSP não seria suficiente para resolver o problema P vs NP diretamente Isso porque embora o TSP seja NPhard ele não está necessariamente em NP Ou seja não é possível afirmar que o TSP pode ser resolvido em tempo polinomial apenas porque há algoritmos polinomiais para resolver problemas em NP No entanto a prova da inexistência de um algoritmo de tempo polinomial para o TSP seria uma evidência significativa de que P NP Isso ocorre porque se houvesse um algoritmo de tempo polinomial para o TSP então haveria um algoritmo de tempo polinomial para todos os problemas em NP já que o TSP é NPhard Portanto a inexistência de um algoritmo de tempo polinomial para o TSP sugere que não há um algoritmo de tempo polinomial para nenhum problema NPhard o que por sua vez sugere que P NP Em resumo a prova da inexistência de um algoritmo de tempo polinomial para o TSP seria uma evidência significativa de que P NP embora não seja uma prova conclusiva 5 O que representa a classe NC de complexidade e qual o seu relacionamento com a classe P A classe NC do inglês Nicks Class de complexidade representa a classe de problemas que podem ser resolvidos em tempo polinomial usando um número polilogarítmico de processadores em paralelo Em outras palavras um problema pertence a NC se ele pode ser paralelizado de forma eficiente em um número de processadores polilogarítmico O relacionamento entre a classe NC e a classe P é que todo problema em P também está em NC Isso ocorre porque um algoritmo em P pode ser executado em paralelo em um número polinomial de processadores cada um responsável por calcular uma parte do problema Como resultado a classe P é um subconjunto da classe NC No entanto existem problemas em NC que não estão em P Esses são os problemas que podem ser paralelizados de forma eficiente mas não podem ser resolvidos de forma eficiente em um único processador Um exemplo de um problema em NC que não está em P é o problema do circuito hamiltoniano que pede para determinar se um grafo não direcionado possui um circuito hamiltoniano um circuito que passa por todos os vértices do grafo exatamente uma vez O problema do circuito hamiltoniano pode ser resolvido em tempo polinomial usando um algoritmo paralelo eficiente mas não se sabe se ele pode ser resolvido em tempo polinomial em um único processador determinístico Em resumo a classe NC de complexidade é a classe de problemas que podem ser resolvidos de forma eficiente em paralelo usando um número polilogarítmico de processadores Todo problema em P também está em NC mas existem problemas em NC que não estão em P O que representa a classe de complexidade Pcomplete Pcompleto A classe de complexidade Pcomplete Pcompleto representa um conjunto de problemas de decisão em que cada problema pode ser reduzido a qualquer outro problema em P em tempo polinomial Em outras palavras um problema é Pcompleto se ele é tão difícil quanto qualquer problema em P Em particular se um problema Pcompleto puder ser resolvido em tempo polinomial então todos os problemas em P também poderão ser resolvidos em tempo polinomial Portanto um problema Pcompleto é tão difícil quanto qualquer problema em P e pode ser considerado um representante de todos os problemas em P Uma consequência importante da definição de Pcompleto é que se um problema pertence tanto a P quanto a NP e se houver um problema Pcompleto que pode ser reduzido a ele então esse problema NP também será Pcompleto Isso ocorre porque todos os problemas em NP podem ser reduzidos em tempo polinomial a um problema NPcompleto e se um problema NPcompleto pode ser reduzido a um problema P completo que pertence a P então ele também pertence a P Os problemas mais conhecidos que são Pcompletos incluem o problema do caixeiro viajante o problema da mochila o problema da satisfatibilidade booleana SAT entre outros A identificação de problemas Pcompletos é importante porque ajuda a entender a complexidade de vários problemas e pode ajudar a identificar limites para a solução eficiente de problemas computacionais Atividade 7 Teoria da Computação 7a Etapa do Curso de Ciência da Computação FCI Mackenzie 1 Fazer um diagrama explicitando a localização do teste de primalidade em termos das classes P e NP Podemos localizar o teste de primalidade em termos das classes P e NP da seguinte maneira O problema da primalidade pertence a NP uma vez que um possível certificado da primalidade de um número é uma lista dos fatores primos do número e este certificado pode ser verificado em tempo polinomial Não se sabe se o problema da primalidade pertence a P ou é NPcompleto No entanto existe um algoritmo determinístico polinomialmente limitado conhecido como teste de primalidade de AKS que pode testar se um número é primo em tempo polinomial Isso sugere que o problema da primalidade pode estar em P No entanto o teste de primalidade de AKS tem uma complexidade assintótica muito alta o que o torna impraticável para a maioria dos tamanhos de entrada Dessa forma o problema da primalidade está em NP mas ainda não se sabe se ele está em P O teste de primalidade de AKS é um algoritmo determinístico polinomialmente limitado que sugere que o problema da primalidade pode estar em P mas não está claro se existem outros algoritmos mais eficientes que possam resolver o problema de forma determinística em tempo polinomial 2 Por que P está necessariamente incluído em NP P está necessariamente incluído em NP porque todos os problemas em P também estão em NP Em outras palavras se um problema pode ser resolvido em tempo polinomial determinístico então ele pode ser resolvido em tempo polinomial não determinístico Isso ocorre porque um algoritmo não determinístico pode adivinhar a resposta certa para um problema em tempo polinomial e depois verificar se essa resposta é correta em tempo polinomial Como qualquer problema que pode ser resolvido em tempo polinomial determinístico também pode ser resolvido em tempo polinomial não determinístico todos os problemas em P também estão em NP Para dar um exemplo considere o problema da ordenação É bem conhecido que a ordenação pode ser resolvida em tempo polinomial determinístico usando algoritmos como o merge sort e o quicksort No entanto também é possível resolver o problema da ordenação em tempo polinomial não determinístico Basta adivinhar uma permutação aleatória dos elementos da lista e verificar em tempo polinomial se a permutação está ordenada corretamente Como resultado o problema da ordenação está em P e também está em NP 3 Um subconjunto I de nós de G é um conjunto independente também conhecido como anticlique se nenhum par de nós de I está conectado por um arco de G Um subconjunto independente é máximo se ele for o maior subconjunto independente de nós deste grafo Por exemplo no grafo abaixo um grafo de Petersen generalizado os 9 nós acinzentados formam o máximo conjunto independente de nós do grafo Sabese que a determinação do máximo conjunto independente de um grafo qualquer é um problema NP Completo Supondo que se conseguiu provar que não existe um algoritmo de tempo polinomial para o problema isso tem alguma consequência a respeito do problema P vs NP Sim a prova da inexistência de um algoritmo de tempo polinomial para o problema de determinar o máximo conjunto independente de um grafo teria importantes consequências em relação ao problema P vs NP Em primeiro lugar é importante notar que a determinação do máximo conjunto independente é um problema NPcompleto o que significa que é improvável que exista um algoritmo eficiente para resolvêlo em todos os casos No entanto a prova da inexistência de um algoritmo de tempo polinomial para esse problema seria uma evidência significativa de que P NP Isso ocorre porque se houvesse um algoritmo de tempo polinomial para determinar o máximo conjunto independente de um grafo então haveria um algoritmo de tempo polinomial para todos os problemas em NP já que a determinação do máximo conjunto independente é NPcompleto Portanto a inexistência de um algoritmo de tempo polinomial para determinar o máximo conjunto independente de um grafo sugere que não há um algoritmo de tempo polinomial para nenhum problema NPcompleto o que por sua vez sugere que P NP Em resumo a prova da inexistência de um algoritmo de tempo polinomial para determinar o máximo conjunto independente de um grafo seria uma evidência significativa de que P NP embora não seja uma prova conclusiva 4 Conforme definimos um problema B é NPHard ou NPDifícil se todo problema A NP é redutível polinomialmente a B Por exemplo sabese que o TSP Travelling Salesman Problem Problema do Caixeiro Viajante é NPHard Supondo que se conseguiu provar a inexistência de um algoritmo de tempo polinomial para o problema isso tem alguma consequência a respeito do problema P vs NP Sim a prova da inexistência de um algoritmo de tempo polinomial para o problema TSP que é NPhard teria importantes consequências em relação ao problema P vs NP Em primeiro lugar a prova da inexistência de um algoritmo de tempo polinomial para o TSP não seria suficiente para resolver o problema P vs NP diretamente Isso porque embora o TSP seja NPhard ele não está necessariamente em NP Ou seja não é possível afirmar que o TSP pode ser resolvido em tempo polinomial apenas porque há algoritmos polinomiais para resolver problemas em NP No entanto a prova da inexistência de um algoritmo de tempo polinomial para o TSP seria uma evidência significativa de que P NP Isso ocorre porque se houvesse um algoritmo de tempo polinomial para o TSP então haveria um algoritmo de tempo polinomial para todos os problemas em NP já que o TSP é NPhard Portanto a inexistência de um algoritmo de tempo polinomial para o TSP sugere que não há um algoritmo de tempo polinomial para nenhum problema NPhard o que por sua vez sugere que P NP Em resumo a prova da inexistência de um algoritmo de tempo polinomial para o TSP seria uma evidência significativa de que P NP embora não seja uma prova conclusiva 5 O que representa a classe NC de complexidade e qual o seu relacionamento com a classe P A classe NC do inglês Nicks Class de complexidade representa a classe de problemas que podem ser resolvidos em tempo polinomial usando um número polilogarítmico de processadores em paralelo Em outras palavras um problema pertence a NC se ele pode ser paralelizado de forma eficiente em um número de processadores polilogarítmico O relacionamento entre a classe NC e a classe P é que todo problema em P também está em NC Isso ocorre porque um algoritmo em P pode ser executado em paralelo em um número polinomial de processadores cada um responsável por calcular uma parte do problema Como resultado a classe P é um subconjunto da classe NC No entanto existem problemas em NC que não estão em P Esses são os problemas que podem ser paralelizados de forma eficiente mas não podem ser resolvidos de forma eficiente em um único processador Um exemplo de um problema em NC que não está em P é o problema do circuito hamiltoniano que pede para determinar se um grafo não direcionado possui um circuito hamiltoniano um circuito que passa por todos os vértices do grafo exatamente uma vez O problema do circuito hamiltoniano pode ser resolvido em tempo polinomial usando um algoritmo paralelo eficiente mas não se sabe se ele pode ser resolvido em tempo polinomial em um único processador determinístico Em resumo a classe NC de complexidade é a classe de problemas que podem ser resolvidos de forma eficiente em paralelo usando um número polilogarítmico de processadores Todo problema em P também está em NC mas existem problemas em NC que não estão em P O que representa a classe de complexidade Pcomplete Pcompleto A classe de complexidade Pcomplete Pcompleto representa um conjunto de problemas de decisão em que cada problema pode ser reduzido a qualquer outro problema em P em tempo polinomial Em outras palavras um problema é Pcompleto se ele é tão difícil quanto qualquer problema em P Em particular se um problema Pcompleto puder ser resolvido em tempo polinomial então todos os problemas em P também poderão ser resolvidos em tempo polinomial Portanto um problema Pcompleto é tão difícil quanto qualquer problema em P e pode ser considerado um representante de todos os problemas em P Uma consequência importante da definição de Pcompleto é que se um problema pertence tanto a P quanto a NP e se houver um problema Pcompleto que pode ser reduzido a ele então esse problema NP também será Pcompleto Isso ocorre porque todos os problemas em NP podem ser reduzidos em tempo polinomial a um problema NPcompleto e se um problema NPcompleto pode ser reduzido a um problema P completo que pertence a P então ele também pertence a P Os problemas mais conhecidos que são Pcompletos incluem o problema do caixeiro viajante o problema da mochila o problema da satisfatibilidade booleana SAT entre outros A identificação de problemas Pcompletos é importante porque ajuda a entender a complexidade de vários problemas e pode ajudar a identificar limites para a solução eficiente de problemas computacionais