24

Can anyone suggest a good and recent survey on counting problems and/or problems that are #P.

Kaveh
  • 21,577
  • 8
  • 82
  • 183
Tayfun Pay
  • 2,598
  • 2
  • 18
  • 45
  • These papers seem to be few and far between. I'd be very interested in a good survey paper on the subject. I noted that Wikipedia doesn't even contain a "List of #P-complete problems". It's also interesting that there were 3 questions today requesting references for counting problems. – bbejot May 05 '11 at 03:24

4 Answers4

14

L. Fortnow. Counting complexity. In L. Hemaspaandra and A. Selman, editors, Complexity Theory Retrospective II, pages 81-107. Springer, 1997

This gives more of the structural complexity point of view (complexity classes, oracles, etc.), and discusses other classes related to #P. Although it's from almost 15 years ago, it's really not that out of date in terms of results.

Joshua Grochow
  • 37,260
  • 4
  • 129
  • 228
  • 1
    @Tayfun: What is missing? Not that I necessarily disagree with you, I am just curious what specifically you would have like to have seen in addition. – Joshua Grochow May 09 '11 at 05:10
12

Try Mark Jerrum's ETH lecture notes. A free version is available from his website here.

RJK
  • 1,952
  • 1
  • 19
  • 27
9

Pinyan Lu published a survey via ECCC in mid 2011. It compares three popular counting frameworks:

  • Counting Graph Homomorphisms,
  • Counting Constraint Satisfaction (#CSP), and
  • the Holant framework
  • (and restrictions of these frameworks).

He also discusses the current dichotomy theorems and the proof techniques used to obtain them.

Xi Chen published a survey as a guest column for SIGACT News in late 2011. It discusses the results and techniques leading up to and including his papers with Jin-Yi Cai and Pinyan Lu on dichotomies for counting graph homomorphisms defined by an undirected target graph with complex weights (arXiv) and nonnegatively-weighted #CSPs (arXiv).

At about the same time, Cai and Chen published a dichotomy for complex-weighted #CSPs (arXiv), which Cai discussed in a guest post on the Godel's Lost Letter and P=NP blog.

Tyson Williams
  • 4,258
  • 2
  • 23
  • 44
3

Another framework of counting problems comes from computing the Tutte polynomial of a graph. In this framework, any two complex numbers defines a counting problem.

The book Matroid Applications devotes chapter 6 to The Tutte Polynomial and Its Applications. The previous link is to a scan of that chapter from the website of James Oxley, one of the coauthors. Last semester, he taught a course based on that chapter.

Another good reference on this topic is this survey-like paper by Welsh.

Tyson Williams
  • 4,258
  • 2
  • 23
  • 44