Formules 3-CNF insatisfaisantes minimales

Je suis actuellement intéressé à obtenir (ou construire) et à étudier des formules 3-CNF insatisfaisantes et de taille minimale. Autrement dit, elles doivent être constituées du moins de clauses (m = 8 de préférence) et de autant de variables distinctes (n = 4 ou plus) que possible, de sorte que la suppression d'au moins une clause rendra la formule satisfaisante.

Plus formellement, toute formule F 3-CNF éligible doit remplir les conditions suivantes:

F est insatisfaisant
F a un minimum (4+) de variables distinctes (ou leur négation)
F a un nombre minimum de clauses (8+)
chaque sous-ensemble approprié de F est satisfaisable (permettant la suppression de toute ou plusieurs clauses arbitraires).
F n'a pas de 2 clauses réductibles à une clause 2-CNF, par exemple (i, j, k) & (i, j, ~k)n'est PAS autorisé (elles se réduisent à (i,j))

Par exemple, avec n = 4, il existe de nombreuses formules 3-CNF à 8 clauses minimales qui ne sont pas satisfaisantes. D'une part, en regardant l'hypercube 4 et en essayant de le recouvrir d'arêtes (2 faces), on peut construire la formule insatisfaisante suivante:

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)

Ceci est considéré comme une formule 3-CNF minimale insatisfaisante car:

C'est insatisfaisant:
- Les articles 1 à 3 sont équivalents à: D or A=B=C
- Les articles 4-6 sont équivalents à: ~D or A=B=C
- Ils impliquent A=B=C, mais par les articles 7 et 8, c'est une contradiction.
Il n'y a que 4 variables distinctes.
Il n'y a que 8 clauses.
La suppression d'une clause la rend satisfaisable.
Aucune clause 2 n'est «réductible» en une clause 2-CNF.

Je suppose donc que mes questions générales ici sont, par ordre d'importance pour moi:

Quelles sont les autres petites formules minimales qui remplissent les conditions ci-dessus? (par exemple, 4,5,6 variables et 8,9,10 clauses)
Existe-t-il une sorte de base de données ou "atlas" de telles formules minimales?
Quels algorithmes non aléatoires existent pour les construire carrément, le cas échéant?
Quels sont les aperçus des caractéristiques de ces formules? Peuvent-ils être comptés ou estimés, étant donné n (# variables) et m (# clauses)?

Merci d'avance pour vos réponses. Je me réjouis de toute réponse ou commentaire.

cc.complexity-theory sat MAF
la source

Chaque clause 3-CNF interdit 1/8-ème des solutions possibles. Il est donc clair que vous avez toujours besoin d'au moins 8 clauses, ou plus si les ensembles de solutions interdites se chevauchent. Puisque votre condition 5 interdit les ensembles non chevauchants de solutions non autorisées pour n = 3, vous avez besoin de plus de 8 clauses pour ce cas: notez que votre exemple n'obéit pas à la condition 5.

András Salamon

Oui, vous avez raison sur tous les points András. 8 clauses sont un minimum requis pour une formule 3-CNF insatisfaisante, et donc la condition 5 peut être un peu trop restrictive à mes fins pour trouver / construire des formules qualifiantes. Je me rends compte que pour n = 3, la condition 5 doit être nécessairement violée, mais a été incluse à des fins d'illustration uniquement. Je suis strictement intéressé par les formules de qualification de taille n = 4 + (c'est-à-dire 4 variables ou plus, mais pas trop de plus). Je vais peut-être rayer la condition 5.

MAF le

Je pense que votre «exemple» avec n = 3 prête à confusion plutôt qu'à illustrer, car (comme András l'a souligné dans son commentaire) ce n'est pas vraiment un exemple de ce que vous demandez dans cette question. L'exemple avec n = 4 est parfaitement fin et illustratif. Pourquoi ne supprimez-vous pas simplement l'exemple avec n = 3?

Tsuyoshi Ito

Bon point, Tsuyoshi. Terminé.

MAF

{x}

$\{x\}$

{x^{'}}

$\{x'\}$

C

$C$

C \cup {v}

$C \cup \{v\}$

C \cup {v^{'}}

$C \cup \{v'\}$

v

$v$

Réponses:

$\lnot A \lor \lnot B \lor \lnot C$ $2$

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

$n=5$ $m=9$

$l_1 \lor l_2 \lor l_3$ $2$

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

$v$ $n$ $m$ $1$ $r=\frac{m}{n}$ $1$ $n$ $r=1$

Giorgio Camerani
la source

Merci pour la réponse, Walter. La procédure que vous décrivez est en effet très utile pour générer des formules min insat encore plus légèrement plus grandes de structure «similaire», c'est-à-dire une fois que vous avez un ensemble de base que vous trouvez avoir des propriétés intéressantes.

MAF

@MAF: Vous êtes les bienvenus. Merci d'avoir posté une question aussi intéressante.

Giorgio Camerani

Je crois que la condition numéro 5 n'est pas vraiment remplie dans votre exemple et ne peut jamais l'être.
Que les clauses suivantes soient équivalentes:

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

Ce qui nous permettra de mapper les clauses de A, B, C et D avec de nouvelles variables p, q, r et s comme la table de vérité suivante:

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
-----------------

Et maintenant, nous pouvons exprimer les clauses de A, B, C et D en termes de p, q, r et s:

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)

Étant donné que toutes les clauses sont affichées et associées à des clauses A, B, C et D. On peut alors affirmer que les clauses p, q, r et s peuvent être réduites à:

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

Ce qui est évidemment violer la condition numéro 5.

Ce que je veux souligner, c'est que même l'exemple ne montre pas explicitement qu'il y a 2 clauses qui peuvent être réduites à 2-CNF, mais est implicitement a (par exemple (~ A, B, D) et (A, ~ B, ~ D)), vous ne pourrez peut-être pas exprimer le 2-CNF avec les variables données, mais lorsque vous introduirez un mappage différent pour le problème, vous pourrez les exprimer.

Khazam Alhamdan
la source