Please enable JavaScript.
Coggle requires JavaScript to display documents.
Problemas P e NP - Coggle Diagram
Problemas P e NP
Problemas que podem ser resolvidos, no pior caso, em tempo polinomial são considerados tratáveis. A sua eficiência é representada por O(p(n)), onde p(n) representa um polinômio
Não é possível resolver problemas intratáveis em um tempo adequado caso a quantidade de inputs seja muito grande.
Dependendo do grau do polinômio, o tempo de execução do algoritmo pode mudar (não existem muitos algoritmos com grau maior que 3)
-
Esse conceito de dificuldade de resolver problemas determina a base da teoria de complexidade computacional
-
Em P existem apenas problemas de decisão. Em alguns casos, é necessário dividir o problema na sua formulação normal em uma sequência de problemas de decisão
Existem os problemas indecidíveis, os quais não podem ser resolvidos por nenhum algoritmo.
Poucos problemas foram provados decidíveis e intratáveis, porém, vários problemas ainda não receberam um algoritmo que o resolva em tempo polinomial, mas este não foi provado como impossível de existir (busca por um circuito hamiltoniano, por exemplo)
-
Etapa de adivinhação não determinística: se supõe uma resposta S que poderia resolver o problema para a instância I.
Etapa determinística de verificação: retorna sim se S for uma possível solução de I e não caso contrário
Problemas NP: problemas que podem ser resolvidos a partir de algoritmos polinomiais não determinísticos
-
-
-
Um problema D1 é dito polinomialmente reduzível a D2 se existir uma função t que transforma as instâncias de um problema nas instâncias outro
O valor das instâncias transformadas por t deve permanecer igual, ou seja, se a instância em D1 for "sim", ela mapeada também deverá ser "sim" em D2
-
Um problema D é dito NP-completo se pertencer a NP e todos os problemas de NP podem ser polinomialmente reduzíveis para D