P vs NP é um dos problemas do Milennium. Quem o resolver ganha 1 MILHÃO DE DÓLARES. Mas qual a relação entre P vs NP e grafos?
Problemas clássicos em grafos como o do caixeiro viajante e da cobertura de vértices são problemas caracterizados como problemas NP-completo.
Mas o que é NP-completo? Um problema A é NP-completo se existe um outro problema A' NP-completo que pode ser reduzível a A.
Para entender melhor o que é P e o que é NP, NP-completo e NP-difícil, abaixo segue um ótimo vídeo explicando tudo.
Nenhum comentário:
Postar um comentário