<p>From the comment above: </p>

<p>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: <a href="http://www.sciencedirect.com/science/article/pii/0020019079900048" rel="nofollow">Rudolf Mathon, A note on the graph isomorphism counting problem, Information Processing Letters, Volume 8, Issue 3, 15 March 1979, Pages 131-136.</a></p>

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

<p><strong>Abstract:</strong>
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. ...</p>

CC BY-SA 3.0
2015-05-13T14:57:07.920Z
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."
András Salamon
CC BY-SA 3.0
2015-05-13T15:05:36.483Z
@AndrásSalamon: good point!!! added it to the answer :-)
Marzio De Biasi
CC BY-SA 3.0
2015-05-13T10:24:38.337Z
2015-05-13T15:05:16.313Z
2015-05-13T15:05:16.313Z
Marzio De Biasi
<p>A couple of obvious ones are Valiant's proof that <a href="https://en.wikipedia.org/wiki/Sharp-P-completeness_of_01-permanent">0-1 matrix permanents are $\#P$-complete</a> (also introducing the class #P) and <a href="https://en.wikipedia.org/wiki/Toda%27s_theorem">Toda's theorem</a> in the form that $P^{\#P}$ contains the polynomial hierarchy. But I'm really writing here to suggest a less obvious choice: the <a href="https://en.wikipedia.org/wiki/Immerman%E2%80%93Szelepcs%C3%A9nyi_theorem">Immerman–Szelepcsényi theorem</a> 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).</p>

CC BY-SA 3.0
2015-05-12T13:19:18.647Z
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
Paramar
CC BY-SA 3.0
2015-05-12T03:04:47.577Z
2015-05-12T03:04:47.577Z
David Eppstein
<p>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?</p>

CC BY-SA 3.0
2015-05-12T02:52:02.360Z
What are your "thoughts already"?
Tyson Williams
CC BY-SA 3.0
2015-05-12T13:16:17.697Z
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.
Paramar
CC BY-SA 3.0
2015-05-12T19:35:21.957Z
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).
Marzio De Biasi
CC BY-SA 3.0
2015-05-12T23:14:14.477Z
@MarzioDeBiasi: That should be an answer!
Huck Bennett
<counting-complexity>
Milestones in counting complexity
Paramar
# Milestones in counting complexity

(Asked by: username_0 on 2015-05-12)

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?

**Tags:** counting-complexity
> **Comments:**
> **username_1**: What are your "thoughts already"?  
> **username_0**: 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.  
> **username_2**: 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).  
> **username_3**: @MarzioDeBiasi: That should be an answer!  

---

## 2 answers

### Answer by username_2 on 2015-05-13. Score: 7

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.](http://www.sciencedirect.com/science/article/pii/0020019079900048)

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. ...

> **Comments:**
> **username_4**: 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."  
> **username_2**: @AndrásSalamon: good point!!! added it to the answer :-)  

---

### Answer by username_5 on 2015-05-12. Score: 7

A couple of obvious ones are Valiant's proof that [0-1 matrix permanents are $\#P$-complete](https://en.wikipedia.org/wiki/Sharp-P-completeness_of_01-permanent) (also introducing the class #P) and [Toda's theorem](https://en.wikipedia.org/wiki/Toda%27s_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](https://en.wikipedia.org/wiki/Immerman%E2%80%93Szelepcs%C3%A9nyi_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).

> **Comments:**
> **username_0**: 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  

---

