#SAT auf # MONOTONE-2SAT reduzieren

8

Das Problem # MONOTONE-2SAT ist bekanntermaßen # P-vollständig. Dies bedeutet, dass #SAT darauf reduziert werden kann. Meine Frage lautet: Wenn eine # SAT- Instanz , welche Transformation konvertiert in die entsprechende # MONOTONE-2SAT-Instanz ?FF 'FF′

Eine zweite Frage ist: Lassen‚die Anzahl der Lösungen von und lassen die Anzahl der Lösungen von seinem . Ist ? Oder müssen wir eine Rücktransformation verwenden, die in umwandelt ?F ' KK′F′KK ' = K K ' K.FK′=KK′K

cc.complexity-theory ds.algorithms complexity-classes sat Giorgio Camerani
quelle
Könnten Sie bitte motivieren, warum Sie gegen diese Frage gestimmt haben?
Giorgio Camerani
Ich bin nicht derjenige, der die Frage abgelehnt hat, aber ich werde nicht überrascht sein, wenn jemand der Meinung ist, dass die Frage zu grundlegend ist.
Tsuyoshi Ito
Das glaube ich nicht. Es ist nicht grundlegender als einige andere Fragen, die auf dieser Website aufgeworfen werden. Trotzdem kann eine Frage, auch wenn sie grundlegend ist, hilfreich sein. Meine Fragen zu Untergrenzen für #SAT- und SAT-Lösungscluster können ebenfalls als sehr grundlegend angesehen werden, wurden jedoch nicht abgelehnt.
Giorgio Camerani
Die erste Frage ist ziemlich einfach: Im Wesentlichen haben Sie gefragt, was eine Reduzierung ist. Die zweite Frage hat mich auch einmal gefangen, aber sie wird durch richtiges Denken gelöst. Der springende Punkt meiner Antwort ist, dass die Frage einfach ist . Wenn Sie nach dem Lesen meiner Antwort immer noch der Meinung sind, dass die Frage auf dem richtigen Niveau ist, ist meine Antwort wahrscheinlich schlecht geschrieben.
Tsuyoshi Ito
1
Walter, Tsuyoshi, während diese Diskussion hilfreich ist, ist ein besserer Ort dafür auf meta.cstheory.stackexchange.com. Warum diskutieren Sie das nicht dort und fügen hier einen Link zu dieser Diskussion hinzu? FWIW, ich denke, die Frage ist relativ harmlos, aber ein bisschen mehr von "warum ich frage" wäre hilfreich gewesen.
Suresh Venkat

Antworten:

7

Was die erste Frage betrifft, so ist dies eine Reduzierung. Informationen zum Reduzieren von # 3SAT auf # Monotone-2SAT finden Sie im Nachweis der # P-Vollständigkeit von # Monotone-2SAT [Val79b], der auf der # P-Vollständigkeit von Permanent [Val79a] basiert. Um #SAT auf # 3SAT zu reduzieren, ist Cooks Reduzierung von Problemen in NP auf 3SAT sparsam und reduziert daher #SAT auf # 3SAT.

Die Antwort auf die zweite Frage lautet nein. Die Reduzierung von [Val79a] von # 3SAT auf Permanent bewahrt nicht die Anzahl der Lösungen. Wenn darüber hinaus eine Reduzierung von #SAT auf # Monotone-2SAT (oder Permanent) bekannt wäre, bei der die Anzahl der Lösungen erhalten bleibt, würde dieselbe Reduzierung die Entscheidungsversion von SAT auf die Entscheidungsversion von Monotone-2SAT (oder Bipartite Matching) reduzieren. impliziert P = NP.

Verweise

[Val79a] Leslie G. Valiant. Die Komplexität der Berechnung der permanenten. Theoretical Computer Science , 8 (2): 189–201, 1979. http://dx.doi.org/10.1016/0304-3975(79)90044-6

[Val79b] Leslie G. Valiant. Die Komplexität von Aufzählungs- und Zuverlässigkeitsproblemen. SIAM Journal on Computing , 8 (3): 410–421, August 1979. http://dx.doi.org/10.1137/0208032

Tsuyoshi Ito
quelle
Vielen Dank für Ihre Hinweise auf [Val79b] und [Val79a]. Was die zweite Antwort betrifft, kann ich sie nicht verstehen: Wenn ein Problem # P-vollständig ist, kann es verwendet werden, um jedes andere Problem in #P zu lösen. Angenommen, ich möchte #SAT lösen: Ich möchte die Anzahl K der Lösungen einer gegebenen Formel F kennen. Dazu reduziere ich F auf eine Instanz F 'von # MONOTONE-2SAT und erhalte dann die Anzahl K' der Lösungen zu F '. Wenn mir das Wissen um K 'nicht hilft, K zu kennen (dh das Lösen von # MONOTONE-2SAT hilft mir nicht, #SAT zu lösen), wie kann # MONOTONE-2SAT # P-vollständig sein? Warum soll ich das alles tun, wenn es #SAT nicht löst?
Giorgio Camerani
Lassen Sie mich einen Nebenkommentar ausdrücken. Ist es möglich, dass ich 40 Dollar bezahlen muss, um einen Artikel zu lesen, der 31 Jahre alt ist? Ich finde das absurd und gegen den Geist der Wissenschaft. Ich würde zustimmen, wenn der Artikel 10-15 Jahre alt wäre, da er als "patentierte" Entdeckung angesehen werden kann. Aber für einen 31 Jahre alten Artikel zu bezahlen, ist meiner Meinung nach eine Schande. Könnte mich jemand auf eine kostenlose Version davon verweisen?
Giorgio Camerani
1
Für die zweite Antwort ist es möglich, K aus K '(und F) zu berechnen; Andernfalls wäre eine Abbildung von F auf F 'keine Reduzierung. Ihre Frage ist jedoch, ob es möglich ist, eine Reduktion vorzunehmen, so dass K = K 'ist. Die Antwort ist, dass es nicht möglich ist.
Tsuyoshi Ito
@ Tsuyoshi Ito: Ein weiterer Kommentar zu Ihrer zweiten Antwort. Die gleiche Anzahl von Lösungen bedeutet nicht, dass der gleiche Lösungsraum vorhanden ist. Eine Instanz A kann die gleiche Anzahl von Lösungen wie eine Instanz B haben, aber die Lösungen von B können im Lösungsraum auf völlig andere Weise verteilt sein.
Giorgio Camerani
1
Ich kenne keine frei verfügbaren Exemplare der von mir zitierten Artikel. Ein Beweis für die # P-Vollständigkeit von Permanent finden sich in vielen Lehrbüchern zur rechnerischen Komplexität, die in Bibliotheken erhältlich sein können: z. B. Computational Complexity von Papadimitriou, Computational Complexity: Eine konzeptionelle Perspektive von Goldreich und Computational Complexity: Ein moderner Ansatz von Arora und Barak einen Beweis enthalten. (mehr)
Tsuyoshi Ito