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.