Validité de la réduction (3-SAT)
-
01-11-2019 - |
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