Lista 5

1. Mostre uma redução de SAT com cláusulas com no máximo três literais para 3-SAT que não inclua novas aparições de variáveis já usadas. Garanta que cada nova variável aparece não mais que 3 vezes na fórmula resultante.

2. Mostre que 2-SAT está em P.
   Dica: A partir de uma fórmula f do 2-SAT, construa um grafo orientado cujo conjunto de vértices consiste de cada variável de f e sua negação e há um arco de ¬ x para y e um arco de ¬ y para x se e somente se há uma cláusula (x ou y) em f.
   Antes de descrever um algoritmo que resolva 2-SAT em tempo polinomial, mostre o grafo correspondente a f = (¬ x₁ ou x₂)(x₁ ou x₃)(¬ x₂ ou x₃).

3. NAE 3-SAT (not all equal 3-SAT) consiste da seguinte variante do 3-SAT: dada uma fórmula CNF em que cada cláusula tem exatamente 3 literais, existe uma atribuição de valores às variáveis tal que, em toda cláusula, exista pelo menos um literal verdadeiro e um falso?
   Prove que NAE 3-SAT é NP-completo.
   Dica: Modifique a redução de CIRCUIT SAT para SAT e obtenha uma redução de CIRCUIT SAT para NAE 3-SAT.

4. [9.5.2] Dê uma redução direta de SAT para 3-SAT. (Isto é, dada uma cláusula com mais que 3 literais, mostre como reescrevê-la como um conjunto equivalente de cláusulas com no máximo 3 literais.) Se necessário, utilize variáveis novas.

5. [9.5.3] Mostre que a versão do 3-SAT em que queremos uma atribuição de valores às variáveis que deixe exatamente um literal verdadeiro em cada cláusula - ONE-IN-THREE-SAT - é NP-completo.

6. Em aula, vimos uma redução de MAX BISSECTION para BISSECTION WIDTH. É possível modificar essa redução para que funcione do MAXCUT para o MINCUT? O que acontece de errado?

7. Considere os seguintes problemas.

   SET COVERING (cobertura por conjuntos):
   Dados:
   - uma família F = {S₁,...,S_n} de subconjuntos de um conjunto finito U;
   - um inteiro positivo k.
   Pergunta: existem <= k conjuntos de F cuja união é U?

   SET PACKING (empacotamento de conjuntos):
   Dados:
   - uma família F = {S₁,...,S_n} de subconjuntos de um conjunto finito U;
   - um inteiro positivo k.
   Pergunta: existem >= k conjuntos de F 2 a 2 disjuntos?

   EXACT COVER BY 3-SETS (cobertura exata por triplas):
   Dada: uma família F = {S₁,...,S_n} de subconjuntos de um conjunto finito U tal que |U|=3m para algum m e |S_i|=3 para todo i.
   Pergunta: existem m conjuntos de F cuja união é U?

   Mostre que EXACT COVER BY 3-SETS é NP-completo exibindo uma redução (simples) de 3DM para EXACT COVER BY 3-SETS. Deduza que SET COVERING e SET PACKING são NP-completos, mostrando reduções de EXACT COVER BY 3-SETS para cada um desses problemas.

8. Considere o seguinte problema.

   0-1 INTEGER PROGRAMMING (programação inteira 0-1):
   Dados:
   - uma matriz racional A_mxn;
   - um vetor racional b com m coordenadas.
   Pergunta: existe um vetor x inteiro 0-1 com n coordenadas tal que Ax<=b?

   Mostre que 0-1 INTEGER PROGRAMMING é NP-completo.
   Dica: Faça uma redução de SET COVERING para 0-1 INTEGER PROGRAMMING, escrevendo um sistema do tipo Ax<=b que tem solução inteira se e somente se existe uma cobertura por conjuntos com no máximo k conjuntos (ou seja, sse existe uma solução para a dada instância do SET COVERING). Faça a coordenada i do vetor x, denotada por xⁱ, valer 1 ou 0, indicando se o conjunto correspondente S_i faz ou não parte da solução.