3
$\begingroup$

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?

$\endgroup$
  • 4
    $\begingroup$ What are your "thoughts already"? $\endgroup$ – Tyson Williams May 12 '15 at 2:52
  • 1
    $\begingroup$ 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. $\endgroup$ – Paramar May 12 '15 at 13:16
  • 2
    $\begingroup$ 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). $\endgroup$ – Marzio De Biasi May 12 '15 at 19:35
  • $\begingroup$ @MarzioDeBiasi: That should be an answer! $\endgroup$ – Huck Bennett May 12 '15 at 23:14
8
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ 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." $\endgroup$ – András Salamon May 13 '15 at 14:57
  • $\begingroup$ @AndrásSalamon: good point!!! added it to the answer :-) $\endgroup$ – Marzio De Biasi May 13 '15 at 15:05
7
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – Paramar May 12 '15 at 13:19

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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