Vérification des solutions uniques de SAT

25

Considérez le problème suivant: étant donné une formule CNF et une affectation qui satisfait cette formule, y a-t-il une autre affectation satisfaisante pour cette formule?

Quelle est la complexité de ce problème? (C'est sûrement en NP, mais est-il aussi difficile en NP?)

Que se passe-t-il si vous ne recevez pas l'affectation et que vous souhaitez simplement décider si la formule a une affectation satisfaisante unique?

Merci.

cc.complexity-theory np-hardness sat unique-solution J--
la source
13
Votre premier problème est souvent un exercice de devoirs. Astuce: étant donné n'importe quelle formule F, concevoir une formule F 'où l'affectation de tous les zéros la satisfait trivialement, et il existe une deuxième affectation satisfaisante F' si F est satisfiable.
Ryan Williams
1
@ Hsien-Chih Chang, nous avions le nom d'Oded sur la première page avant votre repérage, le repérage n'est pas urgent, ce serait bien si son nom y restait un peu plus longtemps. :)
Kaveh
1
@Kaveh: Oups, désolé. Je suppose que je suppose en quelque sorte qu'il restera et fournira constamment de plus en plus de bonnes réponses, donc son nom apparaîtra fréquemment sur la page principale :)
Hsien-Chih Chang 張顯 之
@ Hsien-Chih Chang, je l'espère aussi. :)
Kaveh

Réponses:

27

Le problème de décider si une formule CNF donnée a une affectation satisfaisante autre que celle donnée est facilement montré comme NP-complet en transformant une formule CNF pour ajouter une solution triviale. Ce problème est appelé «un autre problème de solution (ASP) de SAT» dans [YS03], où il est utilisé pour fournir une preuve systématique que (les versions de décision de) les ASP de nombreux autres problèmes sont également NP-complets.

Le problème de décider si une formule CNF donnée a une affectation satisfaisante unique ou non (vous devez donc répondre «non» si la formule n'a pas d'affectations satisfaisantes ou plus d'une affectation satisfaisante) est complet aux États - Unis . US contient à la fois UP et coNP .

Les références

[YS03] Takayuki Yato et Takahiro Seta. Complexité et exhaustivité de la recherche d'une autre solution et de son application aux énigmes. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E86-A (5): 1052–1060, mai 2003.

Edit : Une version antérieure (révision 1) de cette réponse contenait une confusion entre la version de décision et la version de recherche. Il a été corrigé.

Tsuyoshi Ito
la source
6
Juste une note: La complétude NP d'un "autre problème de solution" est le folklore, connu bien avant 2003. (Peut-être qu'il y a une référence des années 1970, mais la preuve est si facile que j'en doute.)
Ryan Williams
@Ryan: Merci pour la note. J'ai édité la réponse pour clarifier la relation avec [YS03].
Tsuyoshi Ito
22

Je me souviens que Yoram Moses et moi-même avons étudié ce problème au milieu des années 1980 (à la lumière d'une application) et découvert que pour de nombreux problèmes naturels de PNJ, le problème de trouver une deuxième solution / alternative (ou de décider si cela existe) est le PNJ. Nous avons alors découvert que c'était connu, mais je ne me souviens pas de la référence, et nous n'avons pas réussi à en trouver une (c'est-à-dire une qui date du milieu des années 1980) maintenant. Mais je suis sûr que je me souviens bien de ce qui précède.

Juste un commentaire envers Ryan. Le fait qu'un théorème puisse être donné comme exercice dans les classes actuelles ne le rend pas moins attrayant. Il aurait dû être publié dans un article portant un titre adéquat au moment de sa découverte ...

Oded Goldreich

Oded Goldreich
la source
15
Hé, bienvenue à bord! Je suis tellement excité de vous voir ici :)
MS Dousti
12

Ici, j'écris un extrait de l'article suivant:

Valiant, LG et Vazirani, VV 1986. NP est aussi simple que de détecter des solutions uniques. Théor. Comput. Sci. 47, 1 (nov. 1986), 85-93. DOI = http://dx.doi.org/10.1016/0304-3975(86)90135-0

Pour chaque problème NP-complete connu, le nombre de solutions de ses instances varie sur une large plage, de zéro à exponentiellement beaucoup. Il est donc naturel de se demander si l'intractabilité inhérente au problème NP-complet est causée par cette large variation. Nous donnons une réponse négative à cette question en utilisant la notion de réductibilité temporelle polynomiale randomisée. Nous montrons que les problèmes de distinction entre les instances de SAT ayant zéro ou une solution, ou de trouver des solutions aux instances de SAT ayant une solution unique, sont aussi difficiles que SAT, sous des réductions aléatoires.

Je suggère également de consulter le document pertinent:

Beigel, R., Buhrman, H. et Fortnow, L. 1998. NP pourrait ne pas être aussi simple que de détecter des solutions uniques. Dans les actes du trentième symposium annuel de l'ACM sur la théorie de l'informatique (Dallas, Texas, États-Unis, 24 - 26 mai 1998). STOC '98. ACM, New York, NY, 203-208. DOI = http://doi.acm.org/10.1145/276698.276737

MS Dousti
la source
6

DP={(L1∩L2)|L1∈NP,L2∈CoNP}

Andreas Blass et Yuri Gurevich, Sur l'unique problème de satisfiabilité,

Mohammad Al-Turkistany
la source
1
Un petit point: le deuxième problème n'est pas un problème de promesse.
Tsuyoshi Ito du
1
Je l'avais réalisé et corrigé, mais merci de l'avoir repéré quand même!
Tsuyoshi Ito du
6
Soit dit en passant, je n'ai rien copié de votre réponse, donc je n'ai aucune idée de ce à quoi fait référence votre commentaire suivant: "Lorsque vous copiez à partir d'une autre réponse, veuillez l'indiquer." J'ai copié la référence de ma réponse à partir d'un autre poste de la mienne sur MathOverflow ( mathoverflow.net/questions/31251/… ), mais je ne pense pas que vous en parliez .
Tsuyoshi Ito du