23
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – bbejot May 5 '11 at 3:24
13
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ @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. $\endgroup$ – Joshua Grochow May 9 '11 at 5:10
12
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I think I found it for free! ;) $\endgroup$ – Tayfun Pay May 5 '11 at 21:36
9
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Nice! I will read this! $\endgroup$ – Tayfun Pay Sep 16 '11 at 12:44
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.