Ankieta na temat #P i / lub problemów z liczeniem

23

Czy ktoś może zasugerować dobrą i najnowszą ankietę na temat liczenia problemów i / lub problemów, które są #P.

cc.complexity-theory reference-request counting-complexity Tayfun Pay
źródło
Dokumenty te wydają się być nieliczne i dalekie od siebie. Byłbym bardzo zainteresowany dobrą pracą ankietową na ten temat. Zauważyłem, że Wikipedia nie zawiera nawet „Listy problemów # P-zupełnych”. Interesujące jest również to, że dziś były 3 pytania z prośbami o referencje do liczenia problemów.
bbejot

Odpowiedzi:

13

L. Fortnow. Liczenie złożoności . W L. Hemaspaandra i A. Selman, redaktorzy, Retrospektywa teorii złożoności II, strony 81-107. Springer, 1997

To daje więcej punktu widzenia strukturalnej złożoności (klasy złożoności, wyrocznie itp.) I omawia inne klasy związane z #P. Mimo to od prawie 15 lat temu, to naprawdę nie jest , że z dniem pod względem wyników.

Joshua Grochow
źródło
1
@Tayfun: Czego brakuje? Nie dlatego, że niekoniecznie się z tobą nie zgadzam, jestem tylko ciekawy, co konkretnie chciałbyś zobaczyć dodatkowo.
Joshua Grochow
9

Pinyan Lu opublikował ankietę za pośrednictwem ECCC w połowie 2011 r. Porównuje ona trzy popularne struktury liczenia:

  • Liczenie homomorfizmów grafowych,
  • Liczenie zadowolenia z ograniczeń (#CSP) oraz
  • ramy Holanta
  • (i ograniczenia tych ram).

Omawia również obecne twierdzenia dychotomii i techniki dowodowe zastosowane do ich uzyskania.

Xi Chen opublikował ankietę jako kolumnę gościnną dla SIGACT News pod koniec 2011 roku. Omawia wyniki i techniki prowadzące do jego publikacji z Jin-Yi Cai i Pinyanem Lu w sprawie dychotomii do zliczania homomorfizmów wykresów zdefiniowanych przez niekierowany wykres docelowy z wagi zespolone ( arXiv ) i nieujemnie ważone #CSP ( arXiv ).

Mniej więcej w tym samym czasie Cai i Chen opublikowali dychotomię dla #CSPs o złożonej wadze ( arXiv ), którą Cai omówił w gościnnym poście na blogu Lostel i P = NP Godela .

Tyson Williams
źródło
Miły! Przeczytam to!
Tayfun Pay
3

Inna struktura liczenia problemów pochodzi z obliczania wielomianu Tutte wykresu. W tej strukturze dowolne dwie liczby zespolone definiują problem zliczania.

Książka Matroid Applications poświęca rozdział 6 The Tutte Polynomial i jego zastosowaniom . Poprzedni link to skan tego rozdziału ze strony Jamesa Oxleya , jednego ze współautorów. W ostatnim semestrze prowadził kurs oparty na tym rozdziale.

Innym dobrym odniesieniem na ten temat jest ten podobny do ankiety artykuł walijski.

Tyson Williams
źródło