Please enable JavaScript.
Coggle requires JavaScript to display documents.
Problemas P, NP e NP-Completo - Coggle Diagram
Problemas P, NP e NP-Completo
-
-
Classe NP
Problemas de decisão não determinístico em que o a eficiência temporal da fase de verificação é polinomial
-
Classe NP-Completo
-
-
Encontrar um algoritmo de tempo polinomial para um problema NP-completo significa que não há diferença qualitativa entre a complexidade de verificar uma solução proposta e encontrá-la em tempo polinomial
-
Um problema de decisão D1 é polinomialmente redutível para D2 se existir uma função t que transforma instancias de de D1 em instâncias de D2
t mapeia todas as instâncias sim de D1 para instâncias sim de D2 e todas as instâncias não de D1 a instância não de D2
-