Please enable JavaScript.
Coggle requires JavaScript to display documents.
P, NP e NP-Complete - Coggle Diagram
P, NP e NP-Complete
Classe P
-
é um classe de problemas que e pode ser resolvidos em tempo polinomial por algoritmos determinísticos
-
-
-
-
Classe NP
-
é um classe de problemas que e pode ser resolvidos em tempo polinomial por algoritmos não determinísticos polinomial
-
NP - Problemas Completos
definição informal
é um problema NP tão difícil quanto qualquer outro problema NP que pode ser reduzido a ele em tempo polinomial
definição formal
um problema de decisão D1 é considerado polinomialmente redutível a D2, se tem uma função T que transforme instancias de D1 para D2
T mapeia D1 sim para D2 sim", D1 não para D2 não*
-
-
-
algoritmo que resolve um problema em tempo polinomial, se o seu pior caso de eficiência de tempo pertence a O (p (n)) onde p (n) é um polinômio deo tamanho de entrada do problema n
-
-