23
$\begingroup$

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

Improve this question
$\endgroup$
1
  • $\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, 2011 at 3:24

4 Answers 4

Reset to default
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.

Improve this answer
$\endgroup$
1
  • 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, 2011 at 5:10
12
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ I think I found it for free! ;) $\endgroup$
    – Tayfun Pay
    May 5, 2011 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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Nice! I will read this! $\endgroup$
    – Tayfun Pay
    Sep 16, 2011 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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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