Olá para todos,
O final do enunciado do exercício 2, letra b, tá estranho. Esse é o trecho " ...\phi não está em \overline{FÓRMULA-MIN} adivinhando essa fórmula."
Eu verifiquei o enunciado desse exercício no livro traduzido do Sipser e esse trecho aparece "... \phi está em \overline{FÓRMULA-MIN} adivinhando essa fórmula."
Talvez o certo seja como está no livro do Sipser. É isso mesmo?
Outra coisa, alguém pode dar uma dica de como resolver o exercício 1? Eu acho que esse exercício pode ser resolvido de duas formas.
1) Reduzir polinomialmente FORMULA-MIN a outro problema NP-completo. Assim, gasto tempo polinomial para reduzir e gasto tempo polinomial para resolver a redução (P=NP).
2) Usar algum problema NP-completo para obter uma solução polinomial para o FORMULA-MIN.
Eu tentei as duas opções mas falhei nas duas. Existe outra opção? Alguém poderia dar uma ajudinha?
Obrigado.
> Talvez o certo seja como está no livro do Sipser. É isso mesmo?
O livro deve estar certo. Tem um "não" sobrando no enunciado da lista.
> Outra coisa, alguém pode dar uma dica de como resolver o exercício 1?
Acho que o negócio é olhar o argumento usado para mostrar que NONMIN-FORMULA está em NP^{SAT}.
Zé Augusto
O livro deve estar certo. Tem um "não" sobrando no enunciado da lista.
> Outra coisa, alguém pode dar uma dica de como resolver o exercício 1?
Acho que o negócio é olhar o argumento usado para mostrar que NONMIN-FORMULA está em NP^{SAT}.
Zé Augusto
Alvaro, para a possibilidade (1) que você propôs daria para encaixar naquela figura que tem no livro do Garey e Johnson: uma fila enorme de pessoas muito esforçadas não conseguiu até hoje reduzir FÓRMULA-MIN para nenhum problema NP-completo.
A segunda opção parece mais produtiva, ainda mais porque o SAT pode ser usado para determinar a equivalência de duas fórmulas booleanas.
A segunda opção parece mais produtiva, ainda mais porque o SAT pode ser usado para determinar a equivalência de duas fórmulas booleanas.
Acho que ajuda lembrar do exercício 2 da lista 3, que nos diz que se P=NP, então podemos achar uma atribuição que satisfaz a fórmula, caso exista.