Unique 1-en-3 SAT

Question

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

Je connais la valeur de chaque bit de la mission unique car elle a été faite à 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 d'A et B dans l'ordre correct dans les bits d'entrée.

Le nombre de vrais littéraux dans chaque clause est 1, 2 ou 3. Parce que je connais la valeur de chaque bit, je peux dire exactement quels littéraux sont vrais dans chaque clause et les comptent. Par exemple, je sais quelles clauses sont satisfaites par exactement 1 littéral. Et ce littéral fait logiquement une partie de la solution unique.

Ma question est simple: si je supprimais toutes les clauses de plus d'un vrai littéral, la mission sera-t-elle nécessairement unique?

En d'autres termes, si je voulais écrire une preuve de résolution (probablement longuement long) pour démontrer que la solution est unique (un autre problème de solution, dans CO-NP), puis-je l'écrire en utilisant uniquement les clauses avec 1 vrai littéral?

Intuitivement, je pense que oui, mais je suis incapable de défendre mon point de vue, même en pensant à l'équivalent 2SAT.

Answer 1

Considérez le CNF suivant: $$ (A \ lor \ lnot b) \ terre (\ lnot a \ lor b) \ terres (a \ lor b). $$ Il a une affectation satisfaisante unique, $ a= b=top $ , qui satisfait à la dernière clause deux fois.Toutefois, si vous supprimez la dernière clause, vous obtenez une autre affectation satisfaisante, $ a= b=bot $ .