<p>Try <a href="http://www.springer.com/birkhauser/applied+probability+and+statistics/book/978-3-7643-6946-0">Mark Jerrum's ETH lecture notes</a>.  A free version is available from his website <a href="http://www.maths.qmul.ac.uk/~mj/pubs.html">here</a>.</p>

CC BY-SA 3.0
2011-05-05T21:36:08.893Z
I think I found it for free! ;)
Tayfun Pay
CC BY-SA 3.0
2011-05-05T08:44:35.063Z
2011-05-05T22:08:09.590Z
2011-05-05T22:08:09.590Z
RJK
<p>Pinyan Lu published a <a href="http://eccc.hpi-web.de/report/2011/093/" rel="noreferrer">survey</a> via ECCC in mid 2011. It compares three popular counting frameworks:</p>

<ul>
<li>Counting Graph Homomorphisms,</li>
<li>Counting Constraint Satisfaction (#CSP), and</li>
<li>the Holant framework</li>
<li>(and restrictions of these frameworks).</li>
</ul>

<p>He also discusses the current dichotomy theorems and the proof techniques used to obtain them.</p>

<hr>

<p>Xi Chen published a <a href="http://dl.acm.org/citation.cfm?doid=2078162.2078177" rel="noreferrer">survey</a> 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 (<a href="http://arxiv.org/abs/0903.4728" rel="noreferrer">arXiv</a>) and nonnegatively-weighted #CSPs (<a href="http://arxiv.org/abs/1012.5659" rel="noreferrer">arXiv</a>).</p>

<p>At about the same time, Cai and Chen published a dichotomy for complex-weighted #CSPs (<a href="http://arxiv.org/abs/1111.2384" rel="noreferrer">arXiv</a>), which Cai <a href="http://rjlipton.wordpress.com/2012/01/20/is-it-time-to-declare-victory-in-counting-complexity/" rel="noreferrer">discussed</a> in a guest post on the <em>Godel's Lost Letter and P=NP</em> blog.</p>

CC BY-SA 3.0
2011-09-16T12:44:56.320Z
Nice! I will read this!
Tayfun Pay
CC BY-SA 3.0
2011-09-16T01:04:13.903Z
2012-08-13T12:24:17.383Z
2012-08-13T12:24:17.383Z
Tyson Williams
<p>Another framework of counting problems comes from computing the <a href="http://en.wikipedia.org/wiki/Tutte_polynomial" rel="nofollow">Tutte polynomial</a> of a graph.  In this framework, any two complex numbers defines a counting problem.</p>

<p>The book <a href="http://rads.stackoverflow.com/amzn/click/0521381657" rel="nofollow">Matroid Applications</a> devotes chapter 6 to <a href="http://www.math.lsu.edu/~oxley/bryox.pdf" rel="nofollow">The Tutte Polynomial and Its Applications</a>. The previous link is to a scan of that chapter from the <a href="https://www.math.lsu.edu/~oxley/" rel="nofollow">website of James Oxley</a>, one of the coauthors. Last semester, he taught a course based on that chapter.</p>

<p>Another good reference on this topic is <a href="http://www.math.ucdavis.edu/~deloera/MISC/BIBLIOTECA/trunk/Welsh/welsh-tutte-polynomial.pdf" rel="nofollow">this survey-like paper</a> by Welsh.</p>

CC BY-SA 3.0
2012-06-07T02:42:51.150Z
2012-06-07T12:38:25.130Z
2012-06-07T12:38:25.130Z
Tyson Williams
<p>L. Fortnow. <a href="https://lance.fortnow.com/papers/files/counting.pdf" rel="nofollow noreferrer">Counting complexity</a>. In L. Hemaspaandra and A. Selman, editors, Complexity Theory Retrospective II, pages 81-107. Springer, 1997</p>
<p>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 <em>that</em> out of date in terms of results.</p>

CC BY-SA 3.0
2011-05-09T05:10:43.907Z
@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
CC BY-SA 4.0
2011-05-08T18:44:33.887Z
2023-12-06T03:08:50.967Z
2023-12-06T03:08:50.967Z
Joshua Grochow
<p>Can anyone suggest a good and recent survey on counting problems and/or problems that are #P. </p>

CC BY-SA 3.0
2011-05-05T03:24:04.820Z
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
<cc.complexity-theory><reference-request><counting-complexity>
Survey on #P and/or counting problems
Tayfun Pay
# Survey on #P and/or counting problems

(Asked by: username_0 on 2011-05-05)

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

**Tags:** cc.complexity-theory, reference-request, counting-complexity

> **Comments:**
> **username_1**: 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.  

---

## 4 answers

### Answer by username_4 on 2011-05-08. Score: 14 | Accepted answer

L. Fortnow. [Counting complexity](https://lance.fortnow.com/papers/files/counting.pdf). 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.

> **Comments:**
> **username_4**: @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.  

---

### Answer by username_2 on 2011-05-05. Score: 12

Try [Mark Jerrum's ETH lecture notes](http://www.springer.com/birkhauser/applied+probability+and+statistics/book/978-3-7643-6946-0). A free version is available from his website [here](http://www.maths.qmul.ac.uk/~mj/pubs.html).

> **Comments:**
> **username_0**: I think I found it for free! ;)  

---

### Answer by username_3 on 2011-09-16. Score: 9

Pinyan Lu published a [survey](http://eccc.hpi-web.de/report/2011/093/) 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](http://dl.acm.org/citation.cfm?doid=2078162.2078177) 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](http://arxiv.org/abs/0903.4728)) and nonnegatively-weighted #CSPs ([arXiv](http://arxiv.org/abs/1012.5659)).

At about the same time, Cai and Chen published a dichotomy for complex-weighted #CSPs ([arXiv](http://arxiv.org/abs/1111.2384)), which Cai [discussed](http://rjlipton.wordpress.com/2012/01/20/is-it-time-to-declare-victory-in-counting-complexity/) in a guest post on the *Godel's Lost Letter and P=NP* blog.

> **Comments:**
> **username_0**: Nice! I will read this!  

---

### Answer by username_3 on 2012-06-07. Score: 3

Another framework of counting problems comes from computing the [Tutte polynomial](http://en.wikipedia.org/wiki/Tutte_polynomial) of a graph. In this framework, any two complex numbers defines a counting problem.

The book [Matroid Applications](http://rads.stackoverflow.com/amzn/click/0521381657) devotes chapter 6 to [The Tutte Polynomial and Its Applications](http://www.math.lsu.edu/~oxley/bryox.pdf). The previous link is to a scan of that chapter from the [website of James Oxley](https://www.math.lsu.edu/~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](http://www.math.ucdavis.edu/~deloera/MISC/BIBLIOTECA/trunk/Welsh/welsh-tutte-polynomial.pdf) by Welsh.


---

