Kürzeste äquivalente CNF-Formel

Sei eine erfüllbare CNF-Formel mit Variablen und Klauseln. Sei der Lösungsraum von . $F_1$ $n$ $m$ $S_{F_1}$ $F_1$

Betrachten Sie das Problem, mit andere CNF-Formel mit demselben Satz von Variablen wie bestimmen, mit (demselben Lösungsraum wie ), aber mit möglichst wenigen (einzigen) Klauseln Ziel ist es, die Anzahl der Klauseln zu minimieren. Wie viele Literale eine Klausel enthält, ist also nicht relevant. $F_1$ $F_2$ $F_1$ $S_{F_2} = S_{F_1}$ $F_1$

Frage

Hat jemand dieses Problem bereits untersucht? Gibt es irgendwelche Ergebnisse in der Literatur dazu?

Betrachten Sie als Beispiel die folgende CNF-Formel (jede Zeile ist eine Klausel): $F_1$

$x_1 \lor x_2 \lor x_3$
$x_2 \lor x_3 \lor x_4$
$\lnot x_1 \lor x_2 \lor x_4$
$\lnot x_1 \lor x_2 \lor \lnot x_3$
$\lnot x_1 \lor x_3 \lor x_5$
$\lnot x_1 \lor x_2 \lor \lnot x_5$

und die folgende Formel : $F_2$

$x_1 \lor x_2 \lor x_3$
$x_2 \lor x_3 \lor x_4$
$\lnot x_1 \lor x_3 \lor x_5$
$\lnot x_1 \lor x_2$

beide haben den gleichen Lösungsraum, aber während hat Klauseln, hat nur . $F_1$ $6$ $F_2$ $4$

Betrachten Sie die folgende Formel : $F_3$

$x_2 \lor x_3$
$\lnot x_1 \lor x_3 \lor x_5$
$\lnot x_1 \lor x_2$

Der Lösungsraum ist wieder derselbe, jedoch mit nur Klauseln. $3$

cc.complexity-theory co.combinatorics sat formulas Giorgio Camerani
quelle

@tsuyoshi Ich denke, er möchte eine CNF-Formel erhalten, die aus einer Mindestanzahl von Klauseln mit dem gleichen Lösungsraum besteht

Tayfun Pay

@TsuyoshiIto: Ja, ich möchte die Anzahl der Klauseln minimieren. Ich schränke die Anzahl der Literale in jeder Klausel nicht ein.

Giorgio Camerani

Für jede vernünftige Definition von "klein" ist das Problem NP-schwer. Eine CNF-Formel ist nur dann erfüllbar, wenn sie nicht der Formel "False" entspricht, die Nullklauseln enthält.

Jeffs

In Abschnitt 6 von citeseerx.ist.psu.edu/viewdoc/… wird erwähnt, dass das Problem der Bestimmung, ob es eine äquivalente CNF-Formel mit höchstens einer bestimmten Anzahl von Literalen gibt, -complete ist. Ich bin mir nicht sicher, warum Ihre Version, die die Anzahl der Klauseln minimiert, interessant ist, da dies innerhalb eines Faktors von der Formelgröße liegt, wobei die Anzahl der Variablen ist.

Π_{2}^{p}

$\Pi_2^p$

n

$n$

n

$n$

András Salamon am

Ein weiteres aktuelles Ergebnis ist ebenfalls relevant: dx.doi.org/10.1016/j.dam.2011.05.013

András Salamon

Antworten:

Das Problem der Bestimmung, ob es eine äquivalente CNF-Formel mit höchstens einer bestimmten Anzahl von Literalen gibt, ist -complete. Die Version, die die Anzahl der Klauseln minimiert, liegt innerhalb eines Faktors von der Formelgröße, wobei die Anzahl der Variablen ist. Siehe Abschnitt 6 von: $\Pi_2^p$ $n$ $n$

Christopher Umans, Das Minimum-Äquivalent-DNF-Problem und kürzeste Implikanten , JCSS 63 (4), 597–611, 2001. doi: 10.1006 / jcss.2001.1775 ( Preprint )

Ein aktuelles Ergebnis zeigt, dass die Berechnung einer bestimmten Untergrenze für die Größe der kürzesten äquivalenten CNF-Formel (gemessen an der Anzahl der Klauseln, wie Sie angeben) NP-vollständig ist. In diesem Artikel heißt es auch, dass Ihr Problem der Minimierung der Anzahl der Klauseln auch -komplett ist, und zitiert das obige Umans-Papier, obwohl mir der Grund dafür nicht sofort klar ist. $\Pi^p_2$

Ondřej Čepek, Petr Kučera und Petr Savický, Boolesche Funktionen mit einem einfachen Zertifikat für die CNF-Komplexität , DAM 160 (4–5), 365–382, 2012. doi: 10.1016 / j.dam.2011.05.013

András Salamon
quelle

Das Schaltungsminimierungsproblem ist nicht lösbar (siehe die Kommentare unten). Ich denke, Sie interessieren sich auch für die Technik, die einige SAT-Löser anwenden (zumindest in gewissem Maße) und die als SAT-Vorverarbeitung bezeichnet wird. Beispielsweise verwendet der bekannte MiniSAT-Löser einen CNF-Minimierer SatELite, um eine Instanz vorzuverarbeiten . Google Scholar liefert auch viele Ergebnisse für "Sat Preprocessing".

Juho
quelle

Ich dachte, Buchführer und Umans haben 2008 das Problem der Schaltungsminimierung gelöst, indem sie -komplett waren, unter Turing Reductions?

Π_{2}^{p}

$\Pi^p_2$

András Salamon

Umans hat bereits 1998 gezeigt, dass es -hard ist, ein Minimumäquivalent für die CNF-Formel zu finden ( dx.doi.org/10.1006/jcss.2001.1775 ). Der Artikel, den András erwähnt, verallgemeinert dies auf Schaltkreise mit größerer Tiefe.

Σ_{2}^{P}

$\Sigma^P_2$

Jan Johannsen

Die wichtigste Standard- / bekannte Lösung zur CNF-Minimierung in EE ist der Quine-McCluskey-Algorithmus, für den es viele Implementierungen gibt, einige gemeinfrei. Ich verstehe jedoch, dass (im aktuellen Wikipedia-Artikel nicht erwähnt) die meisten auf Heuristiken und gierige Algorithmen zurückgreifen, um Lösungen zu finden, insbesondere für große Formeln, dh sie sind nicht erforderlich. finde die optimale Lösung esp. für große Eingabeinstanzen.

Quine-MCluskey ist eine Verallgemeinerung des Arbeitens mit Karnough-Karten, wobei Diagramme für kleine Instanzen erfolgreich sein können.

und beachten Sie, dass es mehrere optimale Lösungen in Bezug auf äquivalente Formeln mit derselben (minimalen) Klauselgröße geben kann, worauf in einem guten Verweis auf das Subj hingewiesen wird. Das Finden des Minimums reduziert sich anscheinend auf die Auflistung aller implizierten Primzahlen, die im Vergleich zur Größe der ursprünglichen Formel einen massiven exponentiellen Anstieg des Gedächtnisses / "Raums" zur Folge haben können.

vzn
quelle