Redutibilidade de 2 versões do problema de satisfação
-
29-09-2020 - |
Pergunta
Preciso de ajuda com este problema.
.Existem 2 versões do problema de satisfabilidade:
[1] Versão de decisão: Determine se uma fórmula arbitrária f é Satisfatório ou não
[2] Versão de pesquisa: Se uma fórmula arbitrária f é satisfável, uma atribuição de valores de verdade para variáveis na fórmula que faz f Satisfatório.Se f é insatisfatório, retorne nil.
Mostrar que [2] é reduzível para [1].
Eu tenho que provar que o algoritmo do Oracle de [1] implica o de [2] para dizer "[2] é reduzível para [1]".
Eu vejo que [2] é apenas o algoritmo do Oracle de [1], uma vez que discrimina a satisfação de uma fórmula arbitrária f.
Isso pode significar que o algoritmo do Oracle de [1] implica isso de [2]?Se pode, qual seria o motivo?
Solução
Qualquer algoritmo que decide que a satisfomoção de uma fórmula também pode ser usada para encontrar uma tarefa para uma fórmula satisfatória:
Embora nem todas as variáveis sejam atribuídas:
-
Escolha uma variável e escolha o valor 0.
-
Se a fórmula não for mais satisfável, substitua o valor com 1.