Question

J'essaie de montrer qu'une variante spéciale du 3-SAT commune est NP-Complete en réduisant 3-SAT à cette variante spéciale.

Cette variante spéciale fonctionne comme le 3CNF-SAT normal, sauf que toutes les autres clauses sont conjonctives au lieu de disjonctives. Par exemple, une instance de cette variante pourrait être $ (x vee y vee z) wedge (x wedge w wedge k) wedge (y vee neg {} z vee f) $.

ÉDITER:

Est-ce que le suivant fonctionnerait? Si je veux réduire les $ de 3 $, je proposerais une instance de la variante 3-SAT, et via un algorithme exécuté en temps polynomial, transformez toutes les autres clause (les conjonctives) en 3 nouvelles clauses disjonctives comme celles suivantes Exemple.

Instance de variance 3-SAT $ (x vee y vee z) wedge (x wedge w wedge k) wedge (y vee neg {} z vee f) $

Transformation / réduction $ (x vee y vee z) wedge (x vee x vee x) wedge (w vee w vee w) wedge (k vee k vee k) wedge (y vee neg {} z vee f) $

Edit 2:

Ou voulez-vous dire que je devrais le regarder dans l'autre sens?

Si je veux prouver que cette variante 3-SAT est NP-Complete, puis-je par exemple ajouter simplement un nouveau terme trival $ z $ non utilisé dans la liste originale des termes (donnez-le comme une valeur de vérité) et ajouter un Clause $ (z wedge z wEdge z) $ entre toutes les clauses d'origine de l'instance d'origine 3-au satelle?

Pas de solution correcte

Licencié sous: CC-BY-SA avec attribution
Non affilié à cs.stackexchange
scroll top