Existe um algoritmo para reduzir ainda mais o CNFS

Question

Eu tenho uma fórmula booleana em forma normal conjuntiva (CNF): $ (A \ Vee B \ Vee C) \ Wedge (A \ Vee B \ Vee \ Neg C) \ Wedge (x \ Vee y) $

Eu sei que isso pode ser simplificado para: $ (A \ Vee B) \ Wedge (x \ Vee Y) $ .

a) existe um algoritmo para decidir se um CNF já está na forma reduzida ou não?

B) Existe um algoritmo que pode fazer essa redução de maneira mais eficiente do que comparar cada par de cláusulas para ver se qualquer pareamento pode ser reduzido?Desejo automatizar esta redução para qualquer CNF e estou procurando por quaisquer algoritmos que eu possa emprestar / implementar.

Answer 1

a minimização do CNF é difícil;Veja https://cstheory.stackexchange.com/q/9839/5038 .É certamente difícil, e há um sentido em que é "ainda mais difícil".

Uma maneira de obter alguma intuição por que é difícil é que, se o CNF não for satisfatório, sua forma reduzida é "falsa", enquanto se for satisfável, sua forma reduzida é outra coisa.Então, se você tivesse uma maneira eficiente de encontrar uma forma reduzida, isso imediatamente lhe daria uma maneira de dizer se o CNF é satisfatório - uma tarefa que sabemos é NP-Hard.

ver https://cstheory.stackexchange.com/q/9839/5038 e https://en.wikipedia.org/wiki/logic_optimization#circuit_minimization_in_booleean_algebra Para alguns pontos na literaturaalgoritmos para esta tarefa.