Primeiro problema NP-completo

Questões-guia:

1. Que tipos de portas lógicas podem ser usadas em instâncias de CIRCUIT-SAT?
2. Em CIRCUIT-SAT, um único fio pode ligar quantas entradas e quantas saídas de portas lógicas?
3. O que é o fan-out de um fio?  E o fan-in?
4. Se representarmos cada porta lógica de uma instância de CIRCUIT-SAT por um vértice, e colocarmos um arco de p₁ a p₂ sempre que a saída de p₁ estiver ligada à entrada de p₂, qual propriedade este grafo orientado deverá ter?  Quantos vértices de grau de saída 0 este grafo poderá ter?
5. Com relação a instâncias de CIRCUIT-SAT, defina atribuição de valores-verdade, atribuição satisfatória e circuito satisfatível.
6. Defina a linguagem CIRCUIT-SAT.
7. Como se define o tamanho de uma instância de CIRCUIT-SAT?
8. Quais são as 6 partes que formam a configuração de uma máquina no modelo de computação utilizado por Cormen para algoritmos de verificação? Quais destas partes mudam ao longo da execução do algoritmo?  Quais não mudam?
9. O circuito construido a partir de um algoritmo verificador A para uma linguagem L tem quantas cópias do circuito M que implementa a execução de 1 instrução da máquina do modelo?  Qual o tamanho de M em função do tamanho n da entrada e da função T que é um limite superior de tempo para A?

Exercícios:

1. Exercício 34.3-1 do Cormen.
2. Discussão sobre o exercício 34.3-8 do Cormen.