Please enable JavaScript.
Coggle requires JavaScript to display documents.
Problemas P, NP e NP-Completo - Coggle Diagram
Problemas P, NP e NP-Completo
É dito que um algoritmo resolve um problema em tempo polinomial se sua eficiência de pior caso estiver em O(p(n)), onde p(n) é um polinômio do problema de tamanho n de entrada.
Problemas que podem ser resolvidos em tempo polinomial são chamados tratáveis e problemas que não podem ser resolvidos em tempo polinomial são chamados intratáveis.
-
Problemas P e NP
Informalmente, podemos pensar sobre problemas que podem ser resolvidos em tempo polinomial como o conjunto que os teóricos da ciência da computação chamam de P. Uma definição mais formal inclui em P somente problemas de decisões, que são problemas com respostas sim/não.
A classe P é uma classe de decisão de problemas que podem ser resolvida em tempo polinomial por algoritmos determinísticos. Essa classe de problemas é chamada polinomial.
-
É natural querer saber se todo problema de decisão pode ser resolvido em tempo polinomial. E a resposta é não. Na verdade, alguns problemas de decisão não tem solução para nenhum algoritmo. Esses tipos de problemas são chamados indecidíveis, o oposto dos problemas decidíveis que podem ser resolvidos por um algoritmo.
Existem problemas decidíveis porém intratáveis? Sim, mas a qtde. de problemas conhecidos é surpreendentemente pouca.
Contudo, existem muitos problemas importantes, para o qual nenhum algoritmo de tempo polinomial foi encontrado, e nem a impossibilidade de um algoritmo desse tipo foi provada.
-
-
O que todos esses problemas têm em comum é um crescimento exponencial (ou pior) de escolhas, como uma função de tamanho de entrada, pela qual uma solução precisa ser encontrada.
Outra característica comum na vasta maioria dos problemas de decisão, é o fato de que, embora resolver esses problemas seja computacionalmente difícil, checar se uma solução proposta resolve um problema, é, na verdade, computacionalmente fácil.
A observação geral sobre problemas de decisão levou cientistas da computação à uma noção de algoritmos não-determinísticos.
Um algoritmo não-determinístico é um procedimento de dois estágios, que usa, como sua entrada, uma instância I de um problema de decisão e faz o seguinte..
Estágio não-determinístico("adivinhação"): Uma string S arbitrária é gerada e pode ser pensada como uma candidata para a solução da instância I dada.
Estágio determinístico("verificação"): Um algoritmo determinístico pega ambos I e S como sua entrada e saída sim se S representar a solução I.
Nós dizemos que um algoritmo não-determinístico resolve um problema de decisão se e somente se para cada instância sim do problema ele retorna sim em alguma execução.
Finalmente, um algoritmo não-determinístico é dito ser não-determinístico polinomial se a eficiência temporal do seu estágio de verificação for polinomial.
A classe NP é a classe da decisão de problemas que pode ser resolvida por algoritmos não-determinísticos polinomiais. Essa classe de problema é chamada não-determinística polinomial.
A maioria dos problemas de decisão estão em NP. Essa classe inclui todos os problemas em P : P ⊆ NP.
Isso é verdade porque, se um problema está em P, nós podemos usar o algoritmo determinístico de tempo polinomial para resolvê-lo no estágio de verificação de um algoritmo não-determinístico que simplesmente ignora a string S gerada no seu estágio não-determinístico("adivinhação").
Umas das questões abertas mais importantes da teoria da ciência da computação é: P é um apropriado subconjunto de NP , ou estas duas classes são, na verdade, a mesma coisa?
P = NP implicaria que cada um dos centésimos problemas de decisão combinatoriais poderiam ser resolvidos por algoritmos de tempo polinomial, apesar dos cientistas terem falhado em encontrar estes algoritmos mesmo com esforços persistentes.
Problemas NP-Completo
Informalmente, um problema NP-completo é um problema NP que é tão difícil como qualquer outro problema nessa classe, porque, por definição, qualquer outro problema em NP pode ser reduzido em tempo polinomial
Um problema de decisão D1 é dito ser polinomialmente reduzível para um problema de decisão D2, se existir uma função t que transforma instâncias de D1 em instâncias de D2 de forma que:
1. t mapeia todas as instâncias sim de D1, para instâncias sim de D2, e todas as instâncias não de D1 para instâncias não de D2.
-
Essa definição imediatamente implica que se um problema D1 é polinomialmente reduzível para algum problema D2 que pode ser resolvido em tempo polinomial, então o problema D1 também pode ser resolvido em tempo polinomial.
-
-
Primeiramente, é necessário mostrar que o problema em questão está em NP, ou seja, uma string gerada aleatoriamente pode ser checada em tempo polinomial para determinar se ela representa a solução para o problema.
O segundo passo é mostrar que todo problema em NP é reduzível para o problema em questão em tempo polinomial.