Please enable JavaScript.
Coggle requires JavaScript to display documents.
IF672 (2020.1) - Levitin Aluno: Marcos André - Coggle Diagram
IF672 (2020.1) - Levitin Aluno: Marcos André
Limitations of Algorithm Power Cap. 11 (401-409)
(11.3) Problemas P, NP e NP-Completos
Problemas tratáveis (tractable)
Resolvido em tempo polinomial
O(p(n))
Problemas intratáveis (intractable)
Não resolvíveis em tempo polinomial
Complexidade computacional
Problemas P e NP
Classe P
Problemas resolvidos em tempo polinomial
Algoritmos determinísticos
Problemas de decisão (Sim/Não)
Problema pode ser reduzido a uma série de problemas de decisão
Undecidable
Problemas de decisão não resolvíveis
Halting problem
Problemas sem solução polinomial encontrada
Problema do circuito hamiltoniano
Problema do Traveling salesman
Problema de coloração em grafos
Entre outros
É fácil checar se um algoritmo resolve o problema
Algoritmo não-determinístico
Estágios
Não-determinístico ("guessing")
Gera uma solução arbitrária para o problema
Determinística ("Verification")
Checa a validade da solução
Resolve problema de decisão
Adivinha uma solução (pelo menos uma vez)
Verifica corretamente sua validade
Eficiência da verificação é polinomial
Classe NP
Problemas de decisão resolvidos por algoritmos não-determinísticos em tempo polinomial
P é subconjunto de NP
P = NP (?)
Problemas NP-Completos
Problemas mais difíceis do NP
Qualquer problema pode ser reduzido para ele em tempo polinomial
Conceitos
Problema polinomialmente reduzível
4 more items...
Problema de decisão NP-Completo
2 more items...
Problema CNF-satisfabilidade
Expressões booleanas
FNC
Se P for diferente de NP
Existem problemas NP que não estão em P nem são NP-Completos
Mostrar que um problema é NP-Completo
Passos
2 more items...
Sem diferença qualitativa entre qualquer problema de decisão
1 more item...
Focar em um approach que melhore a intratabilidade dos problemas