Was wissen wir über den Phasenübergang von # P-Complete-Problemen?

11

Was ist über den Phasenübergang bei # P-Complete-Problemen bekannt? Gibt es speziell einen anderen Phasenübergang für # DNF-k-SAT und # CNF-k-SAT?

Update:
Wie wir wissen, gibt es in Random k-SAT einen Phasenübergang, bei dem die Lösung des Problems von einfach zu schwierig und wieder zu einfach wechselt. Ich würde gerne wissen, ob es ein solches Phänomen auch für # P-Complete-Probleme gibt. Noch wichtiger ist, wenn es einen Phasenübergang gibt, ist er für # CNF-k-SAT und # DNF-k-SAT gleich?

Ich denke, dass es für # CNF-k-SAT eine Art Phasenübergang gibt. Andererseits glaube ich nicht, dass es für # DNF-k-SAT einen Phasenübergang gibt, und das Problem wird schwieriger, wenn wir weitere Klauseln hinzufügen ...

cc.complexity-theory counting-complexity phase-transition Tayfun Pay
quelle
1
Könnten Sie etwas klarstellen, was Sie unter "dem" # P-Phasenübergang verstehen? Der Phasenübergang für NP-vollständige Probleme wird normalerweise als die Wahrscheinlichkeit angesehen, dass eine zufällige Instanz, die aus einer parametrisierten Verteilung gezogen wird, erfüllt werden kann (z. B. für 3-SAT). Was ist der Übergang für #P? Wann ist ein bestimmter Prozentsatz zufriedenstellend?
user834
Bitte geben Sie auch an, ob Sie versuchen, den genauen Wert zu berechnen, oder ob Sie ungefähre Werte zulassen.
Tyson Williams
1
"Das Problem geht von leicht zu schwer und wieder zu schwer" Sie meinen "leicht zu schwer und wieder zu leicht"?
Tyson Williams
1
Ich bin mir immer noch nicht sicher, welche Menge Sie messen. Der 3-SAT-Phasenübergang (als Beispiel für die Konkretheit) wird als die Wahrscheinlichkeit einer bestehenden Lösung angesehen. dh von mindestens einer vorhandenen Lösung. Wenn also "der" # P-Übergang die Wahrscheinlichkeit einer Anzahl von Lösungen ungleich Null bedeutet, dann sind diese beiden äquivalent. Es gibt auch einen Unterschied zwischen "einfach" und "einer vorhandenen Lösung", da erstere einen Polynomalgorithmus impliziert, während letztere dies nicht tut. Das KKW ist bekannt dafür, dass es fast überall schwierig ist, auch weit weg vom Übergangspunkt.
user834

Antworten:

7

Für die Zählung unabhängiger Mengen gibt es kürzlich einen Beweis für einen rechnerischen Phasenübergang von Allan Sly: http://arxiv.org/abs/1005.5584 (der Algorithmus stammt von Dror Weitz aus dem Jahr 2006; Allan hat die passende Härte bewiesen und mitgewonnen der beste Papierpreis in FOCS'10 dafür)

Beachten Sie, dass es für zufällige 3SAT- und ähnliche Probleme keinen Beweis dafür gibt, dass diese Probleme im geeigneten Intervall tatsächlich schwierig sind. Wenn Sie zu den schwierigeren Zählproblemen gehen, wird es einfacher, die Härte zu beweisen.

Dana Moshkovitz
quelle