Please enable JavaScript.
Coggle requires JavaScript to display documents.
P and NP problems - Coggle Diagram
P and NP problems
-
Justificada por problemas com saída exponencialmente grande e a capacidade de reduzir problemas de otimização a problemas de decisão mais simples
-
Exemplo famoso é o problema de parada de Turing, que determina se um programa irá parar ou continuar indefinidamente em um dado input
-
Problemas decidíveis, mas intratáveis:
Existem, mas são poucos os exemplos conhecidos
Muitos problemas importantes não têm algoritmos em tempo polinomial conhecidos ou provas de impossibilidade
-
Um problema NP-completo é um problema em NP que é tão difícil quanto qualquer outro problema dessa classe porque, por definição, qualquer outro problema em NP pode ser reduzido a ele em tempo polinomial.
Um problema de decisão D1 é dito ser polinomialmente reduzível a um problema de decisão D2 se existe uma função t que transforma instâncias de D1 em instâncias de D2.
Um problema D é dito ser NP-completo se: 1) pertence à classe NP; e 2) todo problema em NP é polinomialmente reduzível a D.
Problemas relacionados estão polinomialmente reduzíveis um ao outro, como demonstrado pelo problema do circuito Hamiltoniano que é polinomialmente reduzível ao problema de viajante de comércio.
CNF-SAT é o primeiro problema NP-completo conhecido. Lida com expressões booleanas na forma normal conjuntiva.
Existem centenas, se não milhares, de exemplos de problemas NP-completos conhecidos pelos cientistas da computação.
É conhecido que, se P = NP, deve existir problemas em NP que não estão em P e não são NP-completos.
Definição de P:
Classe de problemas de decisão que podem ser resolvidos em tempo polinomial por algoritmos determinísticos