Gibt es einen Algorithmus zum Reduzieren von CNFs weiter?

Question

Ich habe eine boolesche Formel in konjunktiver Normalform (CNF): $ (A \ Vee B \ Vee C) \ Wedge (A \ Vee B \ Vee \ neg c) \ wedge (x \ vee y) $

Ich weiß, dass dies vereinfacht werden kann: $ (A \ Vee B) \ wedge (x \ vee y) $ .

a) Gibt es einen Algorithmus, um zu entscheiden, ob ein CNF bereits in der reduzierten Form ist oder nicht?

b) Gibt es einen Algorithmus, der diese Reduktion von einer Weise effizienter machen kann, als jedes Paar von Klauseln zu vergleichen, um zu sehen, ob jedes Paarung reduziert werden kann?Ich möchte diese Reduzierung für jeden CNF automatisieren und auf der Suche nach Algorithmen, die ich ausleihen kann / umsetzen kann.

Answer 1

CNF-Minimierung ist schwer;Siehe https://cstheory.steckexchange.com/q/9839/5038 .Es ist sicherlich np-hart, und es gibt einen Sinn, in dem es "noch schwieriger" ist.

Eine Möglichkeit, eine Intuition zu erhalten, warum es schwer ist, ist, dass, wenn der CNF nicht erfüllt ist, seine reduzierte Form "false" ist, während er erfüllt ist, wenn er erfüllt ist, ist die reduzierte Form etwas anderes.Wenn Sie also einen effizienten Weg haben, um eine reduzierte Form zu finden, würde dies sofort einen Weg geben, um zu sagen, ob die CNF erfüllt ist - eine Aufgabe, die wir kennen, ist np-hart.

siehe https://cstheory.steckexchange.com/q/9839/5038 und https://en.wikipedia.org/wiki/logic_optimization#circuit_minimization_in_boolean_algebra für einige Punkte in die Literatur aufAlgorithmen für diese Aufgabe.