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.

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 P ⊆ NP?  É verdade que NP ⊆ P?
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?

Coloração de arestas

Questões-guia:

1. Como emparceirar n equipes que estejam disputando um campeonato de todos contra todos?  Quantas rodadas são necessárias?
2. Defina os seguintes termos: k-aresta-coloração, coloração própria de arestas, grafo k-aresta-colorável, índice cromático.
3. Para grafos simples G, o que pode dizer sobre a relação entre o índice cromático χ'(G) e o grau máximo Δ(G)?
4. O que é um grafo "classe 1"?  E um grafo "classe 2"?
5. A que classe pertencem os grafos bipartidos?
6. Qual a relação entre χ'(G) e Δ(G) em grafos com arestas múltiplas?
7.  O que é um grafo overfull (transbordante?)  A que classe tais grafos pertencem?
8. O que diz o Teorema de Vizing e quais os elementos principais de sua prova?  Consulte, além do livro de West, adotado nesta disiplina, um paper interessante de Misra e Gries sobre o assunto, publicado em 1990.

Exercícios:

1. Exercício 7.1.1 do West, apenas χ'(G).
2. Calcule o número de 3-aresta-colorações próprias de K_3,3.
3. Mostre um grafo G e uma escolha de emparelhamentos máximos tais que o algoritmo a seguir NÃO forneça o índice cromático de G.