Classes de problemas
Questões-guia:
- Conhece-se um algoritmo polinomial para algum problema NP-completo? Pode-se dizer que não há algoritmo polinomial para um problema NP-completo?
- Às vezes dois problemas com enunciados semelhantes podem ser: um deles polinomial e o outro NP-completo. Dê exemplos.
- O que são as classes P e NP? É verdade que P ⊆ NP? É verdade que NP ⊆ P?
- O que é a classe NPC? Ela é diferente de NP?
- Quais são os principais elementos para mostrar que um problema é NP-completo?
- O que são problemas de decisão? Qual sua relação com problemas de otimização?
- O que é uma redução de um problema A para um problema B?
- Porque precisamos de um primeiro problema NP-completo?
Exercícios:
- Ache um problema de decisão intimamente relacionado ao problema do ciclo hamiltoniano.
- Ache um problema de decisão intimamente relacionado ao problema de coloração de grafos.
- 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?
Nenhum comentário:
Postar um comentário