Please enable JavaScript.

Coggle requires JavaScript to display documents.

Problemas P, NP e NP complete - Coggle Diagram

- - - - Existem alguns algoritmos de decisão que são chamados de intratáveis. Não podem ser resolvidos em tempo polinomial
        
        Existem também problemas em que não se achou um algoritmo em tempo polinomial para resolvê-los, mas também não se encontrou uma prova de que tal algoritmo não possa exsitir
        
        O problema do ciclo Hamiltoniano
        
        O problema do caixeiro viajante
        
        O problema da mochila
        
        O problema da coloração de grafos
        
        Alguns problemas que não são imediatamente de decisão podem ser transformados em tal categoria por meio da subdivisão de etapas do processo de resolução do problema em etapas de decisão
- - - - A etapa seguinte do algoritmo é de verificar se esse chute foi ou não correto
        
        Problemas que podem ser resolvidos por algoritmos não determinísticos e polinomiais são englobados em uma classe chamada de NP problems
        
        A maioria dos problemas de decisão estão em NP. Isso porque P é um subconjunto de NP
        
        Ainda não se sabe ser P é um subconjunto próprio de NP ou se eles, na verdade, são o mesmo conjunto
- - - - Um problema de decisão D é dito estar em NP-Complete se
        
        Ele pertence a NP
        
        Todo problema em NP é reduzível a D em tempo polinomial
        
        Exemplo disso é o problema do ciclo Hamiltoniano, que pode ser reduzido ao problema de decisão do caixeiro viajante