Comment montrer que FacactoSAt est NP-Complete?
-
03-11-2019 - |
Question
$ text {exactonesat} = { phi ; | ; phi ; text {est une formule booléenne} $ $ text {tel qu'il a une affectation satisfaisante avec un seul vrai littéral par clause} } $
J'essaie de réduire le 3SAT à ce problème, mais je ne trouve pas de moyen. J'ai essayé de prendre un petit exemple $ phi = (x_1 vee x_2) wedge ( overline {x_1} vee x_2) $. Dans cet exemple, la formule ne peut être satisfaite que lorsque les deux $ x_1, x_2 $ sont vrais. Comment réduire un tel cas de 3SAT à exactonesat?
Ceci est un exercice de Sanjeev Arora et Barak Boaz: une approche moderne de la complexité, mais pas un exercice de devoirs.
Pas de solution correcte
Licencié sous: CC-BY-SA avec attribution
Non affilié à cs.stackexchange