3SAT unique à un unique 1-in-3SAT

Question

Supposons que j'ai une formule CNF avec des clauses de taille 2 et 3. Il a une affectation satisfaisante unique.

il a été fabriqué à partir d'un circuit de multiplication binaire où j'ai multiplié deux nombres premiers A et B tels que A * B= S où S est un numéro de semi -rime. J'ai ajouté les conditions que A!= 1, B!= 1 et A <= B, puis ajoutez la valeur de S à la formule Assurez-vous que l'affectation est unique. Le seul moyen de satisfaire la formule est de mettre les valeurs des nombres premiers A et B dans l'ordre correct dans les bits d'entrée.

en 1-in-3SAT, nous forcons que exactement 1 littéral devrait être vrai dans chaque triplet et deux autres faux. Si exactement 2 liaisons sont vraies, nous pouvons retourner tous les itéraux de la clause pour obtenir une clause équivalente 1-in-3SAT (en d'autres termes 2-in-3SAT est le même problème).

Observation de base: tandis qu'une clause régulière ou clause élimine une possibilité sur 8, une clause de 1 in-3 élimine 5 possibilités sur 8.

3SAT peut être réduit à 1-en-3 SAT, de sorte que si la formule 3SAT est satisfaite, la formule réduite est donc satisfaite.

Toutefois, les réductions ne semblent pas préserver le nombre d'affectations en introduisant de nouvelles variables sans forcer leur valeur.

canette unique 3SAT être réduit à une unique ...

1. sans connaître la bonne affectation?
2. Sinon, tout en connaissant la bonne affectation?

Answer 1

Oui, une formule 3-SAT $ \ Phi $ peut être transformée en une formule SAT 1 in-3 SAT $ \ phi '$ en préservant le nombre de missions satisfaisantes. Pour éviter les ambiguïtés, je vais utiliser " $ \ vee $ " entre littéraux d'une clause de 3 sata et des virgules entre littéraux d'une clause SAT 1 in-3. < / p>

---

Permettez-moi de montrer de manière préliminaire que, donnée deux littéraux $ A $ A $ et $ B $ , nous pouvons simuler un nouveau type de clause $ (x= a \ wedge b) $ qui force la valeur d'une nouvelle variable x $ x $ pour être $ a \ wedge b $ en utilisant uniquement des contraintes SAT 1 in-3, sans introduire de nouvelle solution.

Considérez les cluases: $$ (\ Overline {b}, c, x) \ coin (a, c, d) \ coin (\ Overline {a}, e, x) \ coin (B, E, F) $$

si $ a=top $ $ et $ b=top $ , puis le 2e et 4ème clauses garantit que $ C= D= E= F=BOT $ . Les 1er et 3ème clauses garantissent ensuite que $ x=TOP $ .

si $ a=top $ et $ b=bot $ , puis le 2e La clause garantit que $ c= d=bot $ . La 1ère clause assure ensuite que $ x=BOT $ . La 3ème clause garantit que $ E=top $ et la 4ème clause implique $ f=bot $ .

Le cas $ a=bot $ et $ b=top $ est symétrique.

si $ a=bot $ et $ b=bot $ , puis le 1er et 3ème clauses impliquent $ c= e= x=bot $ . Les 2e et 4ème clauses assurent $ D= F=TOP $ .

---

Je suis maintenant prêt à transformer une formule $ \ phi $ de 3sat vers une formule $ \ phi '$ < / span> de 1-en-3 sat. Considérez maintenant une clause $ (A \ vee b \ vee c) $ de $ \ phi $ . Cela peut être transformé en clauses équivalentes équivalentes suivantes 1-in-3 SAT:

• Ajoutez une nouvelle variable $ x $ c'est vrai iff $ a $ est faux et $ B $ est vrai. Ceci est codé par la clause $ (x=overline {a} \ coin b) $ .

• Ajouter une nouvelle variable $ y $ c'est vrai iff $ a $ est faux , $ B $ est faux, et $ C $ est vrai. Nous aurons besoin d'une variable supplémentaire $ z $ . La clause $ (z=overline {a} \ wedge \ overline {b}) $ assure que $ z $ < / Span> est vrai si et seulement si $ a $ est faux et $ B $ est faux. Ensuite, la valeur de $ y $ peut être appliquée par la clause $ (y= z \ wedge c) $ .

• si $ (A \ vee b \ vee c) $ est vrai alors au moins un de $ A $ , $ B $ ou $ C $ est vrai. Cela signifie que exactement l'un des $ a $ , $ x $ et $ y $ est vrai. Sur l'inverse, si $ (A \ vee b \ vee c) $ est faux, puis du tout de $ a $ , $ x $ et $ y $ est faux. Cela montre que $ (a \ vee b \ vee c) $ est satisfible si et seulement si $ (A, x, y $ ) est satisfible.

Nous avons ensuite construit une formule équivalente 1-in-3 SAT SAT $ \ phi '$ qui utilise une superset des variables de la formule d'origine 3 sat Classe="Conteneur mathématique"> $ \ Phi $ . Une affectation de vérité aux variables de $ \ phi '$ satisfaire $ \ phi' $ si et seulement si L'affectation limitée aux variables de $ \ phi $ satisfait $ \ phi $ . Par conséquent, si une nouvelle solution à $ \ Phi '$ est introduite, il doit être en raison des variables nouvellement ajoutées x $ x $

n>, $ y $ et $ z $ (un ensemble pour chaque clause).Cependant, les valeurs de ces variables sont complètement déterminées par les valeurs des variables de $ \ phi $ .

.

Answer 2

Une telle réduction est décrite à l'annexe B de Régis Barbanchon, sur un graphique unique 3-Colorabilité et réductions parsimonites dans l'avion .Barbanchon l'attribue à des travaux antérieurs ([9] dans la bibliographie).Ailleurs, j'ai vu une attribution au célèbre papier de Schaefer dans lequel il prouve son célèbre théorème de dichotomie, notamment une réduction de 3SAT à 1-3SAT, censée parcimonious (je n'ai pas vérifié).