Please enable JavaScript.
Coggle requires JavaScript to display documents.
P, NP, NP-Completo - Coggle Diagram
P, NP, NP-Completo
-
NP-Completo
É um problema de NP que é tão difícil quanto qualquuer outro. Qualquer outro problema em NP pode ser reduzido a ele em tempo polinomial.
Se P != NP, deve haver um problema em NP que não está em P ou em NP-completo
Prova: Ser NP, provar que é redutível
Se P = NP, não há diferença entre a complexidade de checar uma solução proposta e achar o tempo polinomial n maioria dos problemas de decisão.
-
P: Conjunto de problemas que podem ser resolvidos em tempo polinomial (problemas de decisão, podem ser resolvidos com sim/não)
Quando não pertence a P, o output tende a ser muito extenso
Mesmos problemas que a princípio não são de decisão, podem ser divididos em partes que são (facilitando o estudo)
Nem todo problema de decisão pode ser resolvido em tempo polinomial, alguns nem podem ser resolvidos (indecidíveis)
-
-
Não se sabe se P é um conjunto de NP ou se são conjuntos separados (os problemas de P são resolvidos da mesma forma, mas não precisam do estágio 1.