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

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

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.

Wypróbuj notatki z wykładu ETH Marka Jerruma . Darmowa wersja jest dostępna na jego stronie tutaj .

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 .

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.