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
scroll top