Classes de problemas

Questões-guia:

1. Conhece-se um algoritmo polinomial para algum problema NP-completo?  Pode-se dizer que não há algoritmo polinomial para um problema NP-completo?
2. Às vezes dois problemas com enunciados semelhantes podem ser: um deles polinomial e o outro NP-completo.  Dê exemplos.
3. O que são as classes P e NP?  É verdade que P ⊆ NP?  É verdade que NP ⊆ P?
4. O que é a classe NPC?  Ela é diferente de NP?
5. Quais são os principais elementos para mostrar que um problema é NP-completo?
6. O que são problemas de decisão?  Qual sua relação com problemas de otimização?
7. O que é uma redução de um problema A para um problema B?
8. Porque precisamos de um primeiro problema NP-completo?

Exercícios:

1. Ache um problema de decisão intimamente relacionado ao problema do ciclo hamiltoniano.
2. Ache um problema de decisão intimamente relacionado ao problema de coloração de grafos.
3. O problema de saber se P=NP é um dos grandes desafios da computação contemporânea.  Qual o valor que o Instituto Clay se comprometeu a pagar ao primeiro que resolver esta questão?