Règle de résolution complète pour 1-in-k SAT

Question

Dans CNF SAT, chaque clause (A ou B ou C ou ...) doit contenir au moins un vrai littéral.La règle de résolution s'applique à la paire de clauses qui ont exactement un littéral opposé.

(A ou B ou C) et (! A ou D ou E)=> (B ou C ou D ou E)

Je dis que cette règle est complète, dans le sens où si une formule n'est pas satisfaite, je peux le prouver en appliquant la règle de manière exhaustive (sur des instances difficiles, une quantité exponentielle de fois) jusqu'à ce qu'une clause vide soit produite.Si une formule a une solution unique, je peux appliquer la règle jusqu'à ce que chaque clause d'unité soit produite.

1-in-k SAT est une variante NP-complète où exactement une variable par clause (A, B, C, ....)= 1 est vraie.Compte tenu d'une paire de clause avec un littéral opposé, et pas de littéral commun, je peux également produire un troisième:

(A, B, C)= 1 et (! A, D, E)= 1=> (B, C, D, E)= 1

question : Cette règle est-elle complète pour des formules 1 in-k 1-in-k non satisfiables et non satisfiables?

Answer 1

Vous traitez la résolution comme s'il s'agissait d'une règle purement syntaxique.Cela fonctionne de cette façon avec des clauses traditionnelles du CNF, car cela correspond à la règle sous-jacente d'inférence.Mais une clause CNF avec la restriction supplémentaire d'un seul littéral autorisé à être vrai ne correspond plus plus à la règle de résolution peut être valablement appliquée à.

L'expression booléenne $ (\ lor b) \ terres (\ lnot {a} \ lor \ lnot {b}) \ terre (\ lnot {A} \ lor b) $ est insatisfaite en tant que formule 1-in-k-sat mais naïvement appliquant la règle de résolution produit $ a= faux, b= true$ comme une solution (incorrecte).