# Milestones in counting complexity

I want to prepare a small presentation with some of the most important results in Counting complexity, continue with recent ones and finish with some interdisciplinary results ,probably with other complexity theory areas. I have some thoughts already. Any paper propositions that should definitively be in?

• Probably my question was rather vague. I start with Valiant's result about the permanent. Because I want to include also papers with algorithmic implications I included some references about almost uniform sampling implying approximate counting. I refer to "random generation of combinatorial structures from a uniform distribution" from Jerrum Valiant Vazirani. I include also the Fpras for the knapsack from Sinclair and Morris, the Fpras from Dyer and the fptas from Vigoda Vempala. Finally, I have refer to Valiant's holographic algorithms very briefly. I am asking for less obvious choices. May 12, 2015 at 13:16
• Perhaps a nice (old) result is the (polynomial-time) equivalence between counting the number of isomorphisms between two graphs and deciding whether two graphs are isomorphic (Rudolf Mathon, A note on the graph isomorphism counting problem, Information Processing Letters, Volume 8, Issue 3, 15 March 1979, Pages 131-136). May 12, 2015 at 19:35
• @MarzioDeBiasi: That should be an answer! May 12, 2015 at 23:14

A couple of obvious ones are Valiant's proof that 0-1 matrix permanents are $\#P$-complete (also introducing the class #P) and Toda's theorem in the form that $P^{\#P}$ contains the polynomial hierarchy. But I'm really writing here to suggest a less obvious choice: the Immerman–Szelepcsényi theorem that space complexity classes are closed under complementation. The statement of the theorem doesn't involve counting but its proof does (more specifically a technique called "inductive counting" that has been used by others since).

• Thanks, but my audience is well aware of it. I would like something more intriguing, not so well known and famous. Check also my comment above in Tyson's comment May 12, 2015 at 13:19

From the comment above:

Perhaps a nice (old) result is the (polynomial-time) equivalence between counting the number of isomorphisms between two graphs and deciding whether two graphs are isomorphic: Rudolf Mathon, A note on the graph isomorphism counting problem, Information Processing Letters, Volume 8, Issue 3, 15 March 1979, Pages 131-136.

Note that this is an "evidence" to the conjecture that GI is not NP-complete:

Abstract: The objective of this note is to show that the problem of recognizing whether or not two graphs are isomorphic and the problem of counting all isomorphisms between the graphs are polynomial-time equivalent. Since no NP-complete problem is known for which checking and counting are polynomial-time reducible to each other this result lends evidence to the conjecture that graph isomorphism is not NP-complete. ...

• It also has an intriguing abstract: "The objective of this note is to show that the problem of recognizing whether or not two graphs are isomorphic and the problem of counting all isomorphisms between the graphs are polynomial-time equivalent. Since no NP-complete problem is known for which checking and counting are polynomial-time reducible to each other this result lends evidence to the conjecture that graph isomorphism is not NP-complete." May 13, 2015 at 14:57
• @AndrásSalamon: good point!!! added it to the answer :-) May 13, 2015 at 15:05