Minimale nicht erfüllbare 3-CNF-Formeln

Ich bin derzeit daran interessiert, 3-CNF-Formeln zu erhalten (oder zu konstruieren) und zu studieren, die nicht befriedigend sind und eine minimale Größe haben. Das heißt, sie müssen aus möglichst wenigen Klauseln (vorzugsweise m = 8) und möglichst wenigen unterschiedlichen Variablen (n = 4 oder mehr) bestehen, so dass das Entfernen von mindestens einer Klausel die Formel erfüllbar macht.

Formal muss jede qualifizierende 3-CNF-Formel F die folgenden Bedingungen erfüllen:

F ist unbefriedigend
F hat eine minimale Anzahl (4+) unterschiedlicher Variablen (oder deren Negation)
F hat eine Mindestanzahl von Klauseln (8+)
Jede richtige Teilmenge von F ist erfüllbar (was das Entfernen von beliebigen Klauseln oder Klauseln ermöglicht).
F hat keine 2-Klauseln, die auf eine 2-CNF-Klausel reduzierbar sind, zB (i, j, k) & (i, j, ~k)ist NICHT erlaubt (sie reduzieren sich auf (i,j))

Zum Beispiel gibt es mit n = 4 viele minimale 8-Klausel-3-CNF-Formeln, die nicht erfüllt werden können. Zum einen kann man durch Betrachten des 4-Hyperwürfels und dem Versuch, ihn mit Kanten (2-Seiten) zu bedecken, die folgende unbefriedigende Formel konstruieren:

1. (~A,  B,  D)
2. (~B,  C,  D)
3. ( A, ~C   D)
4. ( A, ~B, ~D)
5. ( B, ~C, ~D)
6. (~A,  C, ~D)
7. ( A,  B,  C)
8. (~A, ~B, ~C)

Dies ist eine mindestens unbefriedigende 3-CNF-Formel, weil:

Es ist unbefriedigend:
- Die Absätze 1-3 entsprechen: D or A=B=C
- Die Absätze 4-6 entsprechen: ~D or A=B=C
- Sie implizieren A=B=C, aber nach den Abschnitten 7 und 8 ist dies ein Widerspruch.
Es gibt nur 4 verschiedene Variablen.
Es gibt nur 8 Klauseln.
Durch das Entfernen einer Klausel wird diese zufriedenstellend.
Keine 2-Klauseln sind auf eine 2-CNF-Klausel 'reduzierbar'.

Ich schätze, meine allgemeinen Fragen hier sind in der Reihenfolge ihrer Wichtigkeit für mich:

Was sind einige andere kleine Mindestformeln, die die obigen Bedingungen erfüllen? (zB 4,5,6 Variablen und 8,9,10 Klauseln)
Gibt es eine Art Datenbank oder "Atlas" mit solchen Mindestformeln?
Welche nicht zufälligen Algorithmen gibt es, um sie vollständig zu konstruieren, wenn überhaupt?
Was sind einige Einblicke in die Eigenschaften dieser Formel? Können sie mit n (# Variablen) und m (# Klauseln) gezählt oder geschätzt werden?

Vielen Dank im Voraus für Ihre Antworten. Ich freue mich über jede Antwort oder Bemerkung.

cc.complexity-theory sat MAF
quelle

Jede 3-CNF-Klausel verbietet 1/8 der möglichen Lösungen. Es ist klar, dass Sie immer mindestens 8 Klauseln oder mehr benötigen, wenn sich die Sätze nicht zugelassener Lösungen überschneiden. Da Ihre Bedingung 5 nicht überlappende Mengen nicht zugelassener Lösungen für n = 3 verbietet, benötigen Sie für diesen Fall mehr als 8 Klauseln: Beachten Sie, dass Ihr Beispiel Bedingung 5 nicht entspricht.

András Salamon

Ja, Sie haben in allen Punkten Recht, András. 8 Klauseln sind ein erforderliches Minimum für eine nicht erfüllbare 3-CNF-Formel, und daher kann Bedingung 5 für meine Zwecke beim Finden / Konstruieren qualifizierender Formeln etwas zu restriktiv sein. Mir ist klar, dass für n = 3 die Bedingung 5 notwendigerweise verletzt werden muss, aber nur zu Illustrationszwecken aufgenommen wurde. Ich bin streng an qualifizierenden Formeln der Größe n = 4 + interessiert (dh 4 oder mehr Variablen, aber nicht zu viele mehr.). Vielleicht werde ich Zustand 5 zerkratzen.

MAF

Ich denke, dass Ihr „Beispiel“ mit n = 3 eher verwirrend als illustrativ ist, weil es (wie András in seinem Kommentar betonte) nicht wirklich ein Beispiel dafür ist, worüber Sie in dieser Frage fragen. Das Beispiel mit n = 4 ist sehr gut und illustrativ. Warum entfernst du nicht einfach das Beispiel mit n = 3?

Tsuyoshi Ito

Guter Punkt, Tsuyoshi. Getan.

MAF

@MAF: Entfernen von Bedingung 5 führt zu einem trivialen Beispiel: Beginnen Sie mit der nicht erfüllbaren Instanz, die die Klauseln und , und ersetzen Sie dann jede Klausel durch zwei Klauseln und für eine neue Variable , und fahren Sie fort, bis alle Klauseln 3 Literale haben. Dies ergibt eine nicht erfüllbare Formel mit 7 Variablen und 8 Klauseln. Dies zerlegt nur den Lösungsraum in 8 unzusammenhängende Teile, was normalerweise kein interessanter Code ist.

{x}

$\{x\}$

{x^{'}}

$\{x'\}$

C

$C$

C \cup {v}

$C \cup \{v\}$

C \cup {v^{'}}

$C \cup \{v'\}$

v

$v$

András Salamon

Antworten:

Nehmen Sie die Formel in Ihrem Beispiel, entfernen Sie die Klausel und fügen Sie die folgenden Klauseln hinzu: $\lnot A \lor \lnot B \lor \lnot C$ $2$

$\lnot A \lor \lnot B \lor \lnot E$
$\lnot B \lor \lnot C \lor E$

Sie erhalten eine minimal unbefriedigende Formel mit , Bedingung 5. $n=5$ $m=9$

Im Allgemeinen können Sie eine Klausel zufällig auswählen und in Klauseln aufteilen : $l_1 \lor l_2 \lor l_3$ $2$

$l_1 \lor l_2 \lor v$
$l_2 \lor l_3 \lor \lnot v$

Dabei ist eine neue Variable. Jedes Mal, wenn Sie dies tun, werden sowohl als auch um erhöht . Wenn Sie diesen Vorgang wiederholen, können Sie den anfänglichen nicht erfüllbaren Kern "dehnen" und minimale nicht erfüllbare Formeln erhalten (unter Beachtung von Bedingung 5), deren zu tendiert, wenn wächst (was als Formeln ziemlich selten ist) mit sind mit hoher Wahrscheinlichkeit erfüllbar). $v$ $n$ $m$ $1$ $r=\frac{m}{n}$ $1$ $n$ $r=1$

Giorgio Camerani
quelle

Danke für die Antwort, Walter. Das von Ihnen beschriebene Verfahren ist in der Tat sehr hilfreich, um noch geringfügig größere Min-Unsat-Formeln mit „ähnlicher“ Struktur zu generieren, d. H., Sobald Sie einen Kernsatz gefunden haben, der interessante Eigenschaften aufweist.

MAF

@MAF: Gern geschehen. Vielen Dank, dass Sie eine so interessante Frage gestellt haben.

Giorgio Camerani

Ich glaube, die Bedingung Nummer 5 ist in Ihrem Beispiel nicht wirklich gegeben und kann niemals gegeben werden.
Die folgenden Klauseln seien gleichbedeutend:

( p, q) = (~A,B,D)(A,~B,~D)

Damit können wir die Klauseln von A, B, C und D den neuen Variablen p, q, r und s als folgende Wahrheitstabelle zuordnen:

A B C D | p q r s
-----------------
0 0 0 0 | 0 1 0 0
0 0 0 1 | 0 1 0 1
0 0 1 0 | 0 1 1 0
0 0 1 1 | 0 1 1 1
-----------------
0 1 0 0 | 1 0 0 0
0 1 0 1 | 0 0 0 0
0 1 1 0 | 1 0 0 1
0 1 1 1 | 0 0 0 1
-----------------
1 0 0 0 | 0 0 1 0
1 0 0 1 | 1 0 1 0
1 0 1 0 | 0 0 1 1
1 0 1 1 | 1 0 1 1
-----------------
1 1 0 0 | 1 1 0 0
1 1 0 1 | 1 1 0 1
1 1 1 0 | 1 1 1 0
1 1 1 1 | 1 1 1 1
-----------------

Und jetzt können wir die Klauseln von A, B, C und D in p, q, r und s ausdrücken:

1. (~A,  B,  D) = ( p, q,~r, s)( p, q,~r,~s)
2. (~B,  C,  D) = (~p, q, r, s)(~p,~q, r, s)
3. ( A, ~C   D) = ( p,~q,~r, s)(~p, q, r,~s)
4. ( A, ~B, ~D) = ( p, q, r, s)( p, q, r,~s)
5. ( B, ~C, ~D) = ( p,~q,~r,~s)(~p, q,~r,~s)
6. (~A,  C, ~D) = (~p, q,~r, s)(~p,~q, r,~s)
7. ( A,  B,  C) = ( p,~q, r, s)( p,~q, r,~s)
8. (~A, ~B, ~C) = (~p,~q,~r, s)(~p,~q,~r,~s)

Da alle Klauseln angezeigt und mit A-, B-, C- und D-Klauseln verknüpft sind. Dann können wir behaupten, dass die Klauseln p, q, r und s reduziert werden können auf:

( p, q, r)
( p, q,~r)
( p,~q, r)
( p,~q,~r)
(~p, q, r)
(~p, q,~r)
(~p,~q, r)
(~p,~q,~r)

Was offensichtlich gegen die Bedingung Nummer 5 verstößt.

Ich möchte darauf hinweisen, dass auch das Beispiel nicht explizit zeigt, dass es 2 Klauseln gibt, die auf 2-CNF reduziert werden können, sondern implizit (zB (~ A, B, D) und (A, ~ B, ~ D)) können Sie die 2-CNF möglicherweise nicht mit den angegebenen Variablen ausdrücken, aber wenn Sie für das Problem eine andere Zuordnung einführen, können Sie sie ausdrücken.

Khazam Alhamdan
quelle