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.

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.

Reduções

Questões-guia

1. O problema de resolver uma equação numérica de 1o. grau pode ser reduzido a resolver uma equação numérica de 2o. grau.  A fórmula de solução para equações de 2o. grau pode ser usada para resolver equações de 1o. grau?  Como?
2. Defina o que significa L₁ ≤_P L₂ para linguagens binárias L₁ e L₂.
3. O que se pode dizer de L₁ quando L₁ ≤_P L₂ e L₂ ∈ P?
4. Defina o que significa dizer que uma linguagem é NP-completa.  Como se define a classe NPC?
5. O que se pode dizer se houver uma linguagem L tal que L ∈ NPC e L ∈ P?
6. O que se pode dizer sobre NPC se P ≠ NP?
7. Defina o que significa dizer que uma linguagem é NP-difícil.
8. O que se pode dizer de L₂ quando L₁ ≤_P L₂ e L₁ ∈ NPC?

Exercícios:

1. Exercício 34.3-2 do Cormen.
2. Exercício 34.3-3 do Cormen.
3. Exercício 34.3-6 do Cormen.

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.

Classe P

Questões-guia:

1. Porque problemas que podem ser resolvidos em tempo polinomial são considerados "tratáveis"?  Dê três motivos.
2. O que é um problema abstrato?
3. Para que servem codificações?
4. Defina alguns conceitos básicos da teoria de linguagens formais: alfabeto, linguagem, string vazia, linguagem vazia, operações sobre linguagens (união, intersecção, complemento, concatenação).
5. O que é o fecho de uma linguagem L, denotado por L*?
6. O que significa dizer que uma string s é aceita por um algoritmo A?  E o que é s ser rejeitada por A?
7. O que significa dizer que uma linguagem L é aceita por um algoritmo A?  E o que é L ser decidida por A?
8. O que significa dizer que uma linguagem L é aceita (decidida) por um algoritmo A em tempo polinomial?
9. Defina a classe P.

Exercícios:

1. Exercício 34.1-1 do Cormen.
2. Dê uma versão de decisão para o problema de achar uma árvore espalhada mínima num grafo não orientado ponderado.
3. Mostre que se uma linguagem L está em P, então L* também está em P.