Umfrage zu #P und / oder Zählproblemen

23

Kann jemand eine gute und aktuelle Umfrage zum Zählen von Problemen und / oder Problemen, die #P sind, vorschlagen.

cc.complexity-theory reference-request counting-complexity Tayfun Pay
quelle
Diese Papiere scheinen selten zu sein. Ich wäre sehr an einem guten Umfragepapier zu diesem Thema interessiert. Ich habe festgestellt, dass Wikipedia nicht einmal eine "Liste von # P-vollständigen Problemen" enthält. Interessant ist auch, dass es heute drei Fragen gab, bei denen Referenzen für das Zählen von Problemen angefordert wurden.
Bejot

Antworten:

13

L. Fortnow. Komplexität zählen . In L. Hemaspaandra und A. Selman, Herausgeber, Complexity Theory Retrospective II, Seiten 81-107. Springer, 1997

Dies gibt einen größeren Einblick in die strukturelle Komplexität (Komplexitätsklassen, Orakel usw.) und erläutert andere Klassen, die sich auf #P beziehen. Obwohl es vor von fast 15 Jahren, es ist wirklich nicht , dass nicht mehr aktuell in Bezug auf die Ergebnisse.

Joshua Grochow
quelle
1
@ Tayfun: Was fehlt? Nicht, dass ich Ihnen nicht unbedingt zustimme, ich bin nur gespannt, was genau Sie dazu gesehen haben möchten.
Joshua Grochow
12

Probieren Sie Mark Jerrums Vorlesungsskript . Eine kostenlose Version finden Sie auf seiner Website hier .

RJK
quelle
Ich glaube, ich habe es kostenlos gefunden! ;)
Tayfun Pay
9

Pinyan Lu veröffentlichte Mitte 2011 eine Umfrage über ECCC. Sie vergleicht drei beliebte Zähl-Frameworks:

  • Grafische Homomorphismen zählen,
  • Zählen der Constraint-Zufriedenheit (#CSP) und
  • das Holant-Framework
  • (und Einschränkungen dieser Frameworks).

Er diskutiert auch die aktuellen Dichotomiesätze und die Beweistechniken, mit denen sie erhalten werden.

Xi Chen veröffentlichte Ende 2011 eine Umfrage als Gastkolumne für SIGACT News. Sie diskutiert die Ergebnisse und Techniken, die bis einschließlich seiner Arbeiten mit Jin-Yi Cai und Pinyan Lu zu Dichotomien für die Zählung von Homomorphismen von Graphen, die durch einen ungerichteten Zieldiagramm mit definiert werden, geführt haben komplexe Gewichte ( arXiv ) und nichtnegativ gewichtete #CSPs ( arXiv ).

Etwa zur gleichen Zeit veröffentlichten Cai und Chen eine Dichotomie für komplex gewichtete #CSPs ( arXiv ), die Cai in einem Gastbeitrag im Lost Letter und im P = NP- Blog von Godel erörterte .

Tyson Williams
quelle
Nett! Ich werde das lesen!
Tayfun Pay
3

Ein weiteres Framework zum Zählen von Problemen besteht in der Berechnung des Tutte-Polynoms eines Graphen. In diesem Rahmen definieren zwei beliebige komplexe Zahlen ein Zählproblem.

Das Buch Matroid Applications widmet sich in Kapitel 6 dem Tutte-Polynom und seinen Anwendungen . Der vorherige Link führt zu einem Scan dieses Kapitels von der Website von James Oxley , einem der Mitautoren. Letztes Semester unterrichtete er einen Kurs, der auf diesem Kapitel basiert.

Eine weitere gute Referenz zu diesem Thema ist dieses umfrageähnliche Papier von Welsh.

Tyson Williams
quelle