Please enable JavaScript.
Coggle requires JavaScript to display documents.
Problemas N, NP e NP-completos - Coggle Diagram
Problemas N, NP e NP-completos
Um algoritmo resolve um problema em tempo polinomial se sua eficiência de tempo de pior caso pertencer a O(p(n)), onde p(n) é um polinomio do tamanho de entrada do problema n.
Problemas que podem ser resolvidos em tempo polinomial são chamados de TRATÁVEIS e os que não podem, de INTRATÁVEIS
Classe P
-
-
Ex.: Eq-Grau-2, Divisor-Comum-Grande, Subseq-Cresc-Longa, Caminho-Curto, Intervalos-Disjuntos
-
Classe NP
São problemas razoáveis, ou seja, é fácil reconhecer uma solução de uma instância do problema quando se está diante de uma
É a classe de problemas de decisão que podem ser resolvidos por algoritmos polinomiais não determinísticos.
Classe NP-completo
Um problema de decisão D1 é polinomialmente redutível a um problema de decisão D2, se existir uma função t que transforma instâncias de D1 em instâncias de D2 de modo que:
mapeia todas as instâncias sim de D1 para instâncias sim de D2 e todas as instâncias não de D1 para nenhuma instância de D2
-
-