Eine Frage zum # P-vollständigen Nachweis der bleibenden Karte von Ben-Dor / Halevi

14

In der Arbeit von Ben-Dor / Halevi [1] wird ein weiterer Beweis dafür erbracht, dass die bleibende Karte #P-vollständig ist. Im späteren Teil der Arbeit wird die Reduktionskette während der permanente Wert in der Kette erhalten bleibt. Da sich die Anzahl der zufriedenen Zuordnungen einer 3SAT-Formel aus dem permanenten Wert ergibt, reicht es aus, die permanente der endgültigen Matrix zu berechnen . So weit, ist es gut.IntPerm α NoNegPerm α 2PowersPerm α 0/1-Perm Φ 0 / 1#P

IntPermNoNegPerm2PowersPerm0/1-Perm
Φ0/1

Es ist jedoch bekannt, dass die bleibende Zahl einer Matrix gleich der Anzahl perfekter Übereinstimmungen in der zweigeteilten Doppelhülle , dh der Graph aus der Matrix . Und diese Zahl kann effizient berechnet werden, wenn sich herausstellt, dass planar ist (unter Verwendung des Kastelyens-Algorithmus).0/1EING(0EINEINt0)G

Insgesamt bedeutet dies, dass jemand die Anzahl der zufriedenen Zuweisungen einer Booleschen Formel berechnen könnte, wenn der endgültige Graph planar ist.ΦG

Da die Einbettung von stark von der Formel abhängt , besteht die Hoffnung, dass es bestimmte Formeln gibt, die häufiger zu planaren zweigeteilten Hüllen führen. Weiß jemand, ob jemals untersucht wurde, wie groß die Wahrscheinlichkeit ist, dass planar sein wird?GΦG

Da zählen satiesfying Lösungen -komplette, werden die Graphen sicher fast immer nicht planar sein, aber ich kann keine Hinweise zu diesem Thema finden.#P

[1] Amir Ben-Dor und Shai Halevi. Null-Eins-Permanent ist # p-vollständig, ein einfacherer Beweis. In 2. Israel Symposium über Theorie der Computersysteme, Seiten 108-117, 1993. Natanya, Israel.

Etsch
quelle

Antworten:

11

Dieses Thema wurde in den letzten Jahren unter dem Namen Holographic Algorithms von Forschern wie Valiant, Cai, Lu, Xia, Lipton und anderen eingehend untersucht . Grundsätzlich wurden alle nachvollziehbaren Fälle von #CSP (Counting Constraint Compliance Problems) anhand von Dichotomiesätzen identifiziert (FP vs. # P-complete). Insbesondere Matchgate-Berechnungen wurden als die spezifische Klasse von Zählproblemen identifiziert, die auf planaren Graphen nachvollziehbar werden. Siehe zB diesen Link für weitere Referenzen.

Martin Schwarz
quelle
1
ΦEINGEINGΦΦG
2

ΓΓΦ

ΓΦΓ

ΓΦΦ

GΦG

Tyson Williams
quelle