Comment prouver qu'une version de contrainte 3SAT dans laquelle aucun littéral peut se produire plus d'une fois, est résoluble en temps polynomial?

Question

Je suis en train de travailler à une cession (tiré du livre algorithmes - par S. Dasgupta, CH Papadimitriou, et Vazirani UV, chapitre 8, problème 8.6a), et je paraphrase ce qu'il dit:

  

Étant donné que 3SAT reste NP-complet, même si limité aux formules dans lesquelles   chacun apparaît littéral au plus deux fois, montrent que si chacun semble littéral au plus une fois, le problème est résoluble en temps polynomial.

J'ai essayé de résoudre ce problème en séparant les clauses en plusieurs groupes:

1. Les clauses qui n'ont pas une variable en commun avec le reste des clauses
2. Les clauses qui ont seulement 1 variables en commun
3. Les clauses qui avaient 2 variables communes
4. Les clauses qui avaient toutes les 3 variables en commun

Mon raisonnement a été tentée le long des lignes que le nombre de ces groupes est fini (en raison de la restriction imposée ABSENTE être littéral plus d'une fois), et nous pourrions essayer de satisfaire le groupe le plus restreint premier (groupe 4) et puis remplacer le résultat dans les groupes restreints (moins 3, 2 et 1), mais je me suis aperçu que cela n'a pas été tout à fait me faire nulle part, car cela ne diffère pas beaucoup de cas pour la version de contrainte 3SAT dans laquelle chaque littéral peut apparaître au plus deux fois, ce qui a été prouvé NP-complet.

J'ai essayé la recherche en ligne pour toutes les astuces / solutions, mais tout ce que je pourrait faire était ce lien , dans lequel l'indice a déclaré ne pas me faire assez de sens, que je reproduire textuellement ici:

  

Astuce: Comme chaque apparaît littéral au plus une fois, convertir ce problème à l'2SAT - donc temps polynomial, si une affiche de $ de x_i de $ littérale à l'article $ C_J $ et complément de $ x_i $ (soit $ \ overline {x_i } $) à l'article $ C_K $, la construction d'une nouvelle clause clause $ C_J \ lor \ overline {C_K} $.

Les deux $ C_J $ et $ C_K $ ont trois littéraux chacun - C_J Je n'ai pas comment je devrais aller sur le convertir en 2SAT en faisant $ \ lor \ overline {} C_K $ (ou $ \ overline {C_J \ Lor C_K} $ si je l'ai lu à tort).

Toute aide soit l'indice de décryptage, ou de fournir un chemin que je peux explorer serait vraiment apprécié.

Answer 1

Sans perte de généralité, on peut supposer que chaque variable apparaît exactement une fois positivement et négativement exactement une fois (si une variable apparaît une seule fois définir sa valeur pour satisfaire la clause et de supprimer la clause). On peut aussi supposer qu'une variable ne semble pas dans une clause plus d'une fois (si une variable apparaît à la fois dans une clause positive et négative, la clause est satisfaite et peut être retiré). Ceux-ci ne modifiera pas la satisfiabilité.

Utilisez la règle de résolution href="http://en.wikipedia.org/wiki/Resolution_%28logic%29" pour éliminer les variables une par une (depuis chaque variable apparaît exactement une fois positivement et négativement une fois ce processus est déterministe). Si, à tout moment, nous obtenons la clause vide l'ensemble des clauses est insatisfiable, sinon il est satisfiable. En effet:

• résolution est un système complet de preuve propositionnelle (à savoir si une clause est logiquement impliquée par l'ensemble des clauses il est dérivable de l'ensemble des clauses utilisant uniquement la règle de résolution),

• un ensemble de clauses est satisfaisable ssi il implique logiquement la clause vide.

Cet algorithme prendra du temps polynomiale puisque chaque variable est résolu exactement une fois. En particulier, chaque application de la résolution permettra de réduire le nombre total de clauses par un, de sorte que le nombre de clauses n'augmente pas. Par exemple, l'application de la résolution à $ (x \ lor B) \ terre (\ overline {x} \ lor C) \ terre \ points) $ rendements $ (B \ lor C) \ terre \ points $, qui a une moins clause avant que la résolution. En revanche, si vous avez appliqué cela à une formule 3SAT sans restriction quant au nombre d'apparitions de chaque littéral, l'application de la résolution pourrait entraîner le nombre de clauses d'augmenter de façon exponentielle.