Please enable JavaScript.
Coggle requires JavaScript to display documents.
P, NP e NP-Complete - Coggle Diagram
P, NP e NP-Complete
Algoritmo não determinístico
Pega uma possível solução e checa se ela
serve para o problema em questão
NP problems
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" doproblema inicial
A função é computável por um algoritmo polinomial
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
Checar se é possível que a resposta seja true
P problems
Classe de problemas que podem ser
resolvidos em tempo polinomial
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
Decision problems
P = NP?
Problemas resolvidos com tempo polinomial são
tratáveis, e os não resolvidos são intratáveis