Please enable JavaScript.
Coggle requires JavaScript to display documents.
Problemas P, NP e NP-Complete - Coggle Diagram
Problemas P, NP e NP-Complete
Problemas resolvidos com tempo polinomial são tratáveis, e os não resolvidos são intratáveis
P problems
Classe de problemas que podem ser resolvidos em tempo polinomial
Decision problems
Indecidíveis: problemas de decisão que não podem ser resolvidos por nenhum algoritmo
Halting problem
Decidíveis: problemas que podem ser decididos por qualquer algoritmo
Algoritmo não determinístico
Pega uma possível solução e checa se ela serve para o problema em questão
NP problems
A maioria dos decision problems
Inclui todos os problemas P
NP-Complete problems
Se pertence a classe NP e é polinomialmente redutível
Pouco exemplos, pois precisa conhecer todos os problemas
CNF-satisfiability problem
Expressões booleanas
Checar se é possível que a resposta seja true
Um problema de decisão é polinomialmente redutível se existe uma função que transforma suas instâncias de forma que:
A função mapeia todas as instâncias "sim" do problema inicial
A função é computável por um algoritmo polinomial
P = NP ?