Classe NP

Questões-guia:

1. Em aulas anteriores, discutimos a classe NP em termos de algoritmos não determinísticos.  Que abordagem segue o Cormen?
2. Como se define a linguagem HAM-CYCLE?  Em quanto tempo roda o algoritmo ingênuo de testar todos os possíveis ciclos?
3. O que é um algoritmo verificador para uma linguagem?
4. Como se define a classe NP?
5. Como se define a classe co-NP?  É igual à classe NP?

Exercícios:

1. Exercício 34.2-1 do Cormen (fácil).
2. Exercício 34.2-3 do Cormen.
3. Exercício 34.2-8 do Cormen (fácil).
4. Exercício 34.2-10 do Cormen (fácil).
5. Exercício 34.2-11 do Cormen.