Please enable JavaScript.
Coggle requires JavaScript to display documents.
401–409 Problemas P,NP e NP-Completo - Coggle Diagram
401–409 Problemas P,NP e NP-Completo
Definição
Problemas que podem ser resolvidos em tempo polinomial são chamados de tratáveis e os que não podem são chamados de intratáveis
Complexidade computacional teoria que busca classificar problemas de acordo com suas dificuldades inerentes
P e NP
P
-
-
A classe P é a classe de problemas de decisão que podem ser resolvidos em tempo polinomial por algoritmos
Algoritmo não deterministico é um procedimento de dois estagios que toma seus inputs numa instancia I de um problema de decisão
-
-
NP
É a classe de problemas de decisão que pode ser resolvida por algoritmos polinomiais não deterministicos
NP-Completos
Um problema de decisão D1 é dito polinomialmente redutivel a um problema de decisão D2 se existir uma função t que transforma instancias de D1 em instancias de D2
t mapeia todas as instancias sim (com solução) de D2 e todas as instancias não (que não são solução) de D1 para instancias não de D2
-
-