Outros problemas NP-completos

Questões-guia:

1. Mostre que CIRCUIT-SAT ≤_P SAT.  Dica: coloque nomes de variáveis para os fios também, além das entradas.
2. Mostre que SAT ≤_P 3-CNF-SAT.  Dica: a partir de uma árvore sintática para a fórmula, dê nomes de variáveis aos nós internos da árvore, construa cláusulas para cada nó interno, transforme cada cláusula em ≤3-CNF, depois em 3-CNF.
3. Mostre que 3-CNF-SAT ≤_P CLIQUE.  Dica: construa um vértice para cada literal de cada cláusula e ligue literais consistentes em cláusulas distintas.  A fórmula será satisfatível se e somente se o grafo tiver uma clique de tamanho n/3, onde n é o número total de vértices.
4. Mostre que CLIQUE ≤_P VERTEX-COVER.  Dica: use STABLE-SET como intermediário.
5. Mostre que 3-CNF-SAT ≤_P 3-COLOR.  Dica: veja Problema 34-3 do Cormen.

Exercícios:

1. Exercício 34.4-1 do Cormen.
2. Exercício 34.4-2 do Cormen.
3. Exercício 34.4-5 do Cormen.
4. Exercício 34.5-6 do Cormen.