domingo, 30 de setembro de 2012

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 PNP?  É verdade que NPP?
  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?

Nenhum comentário:

Postar um comentário