MC558 - Prova P3

Enunciado distribuído na sala.

Gabarito:

  1. 3-CNF-SAT é NP-completa, conforme visto em classe.

    3-DNF-SAT está em P, portanto não sabemos se é NP-completa.

    3-CNF-TAUT está em P tambem, portanto não sabemos se é NP-completa.

    3-DNF-TAUT é completa para co-NP, portanto não sabemos se é NP-completa.

  2. Pode-se dizer que L2 está em NP. Dado um algoritmo verificador A(x,c) para L1 ∪ L2, podemos definir um algoritmo verificador A' que usa, para cada string x, o mesmo certificado que A, e que pode ser descrito como:

    A'(x,c)
      if A(x,c) then
        if x ∈ L1 then
          return false
        else
          return true
      else
        return false

  3. Há duas partes.

    LONGEST-PATH está em NP: o certificado é um caminho de comprimento k. É fácil testar em tempo polinomial que o objeto dado é um caminho e que tem o comprimento dado.

    Redução de HAM-PATH: dado um grafo G, construa a instância ⟨G, n(G)-1⟩ de LONGEST-PATH. O grafo G possui um caminho hamiltoniano se e somente se esta instância está em LONGEST-PATH.

  4. Há uma estratégia ganhadora para o primeiro jogador: x1=1; se x2=0, entao x3=1; se x2=1 entao x3=0.

Critérios de correção

  1. 0,5 para 3-CNF-SAT.
    1,0 para as outras, divididos em 0,5 pela resposta correta e 0,5 pela justificativa.
  2. Falou que é NP-completa: -1,0.
    Não mostrou algoritmo verificador: -0,5.
  3. Mostrou que está em NP: 1,0.
    Mostrou redução: 1,0.
    Não foram subtraídos pontos para quem usou |V(G)| em vez de |V(G)|-1 para criar a instância de LONGEST-PATH na redução de HAM-PATH.
  4. Não demonstrou estratégia ganhadora por erro em contas: 0,5 por conta correta.

MC558 Home

© 2012 João Meidanis