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?
$\begingroup$
$\endgroup$
4
-
4$\begingroup$ What are your "thoughts already"? $\endgroup$– Tyson WilliamsMay 12, 2015 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$– ParamarMay 12, 2015 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 BiasiMay 12, 2015 at 19:35
-
$\begingroup$ @MarzioDeBiasi: That should be an answer! $\endgroup$– Huck BennettMay 12, 2015 at 23:14
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
There has been a series of breakthroughs on Dichotomy Theorems by Professor Jin-Yi Cai https://rjlipton.wordpress.com/2012/01/20/is-it-time-to-declare-victory-in-counting-complexity/ Another dichotomy theorem https://rjlipton.wordpress.com/2014/06/23/counting-edge-colorings-is-hard/
https://rjlipton.wordpress.com/2011/02/14/classifying-papers-on-classifying-problems/
https://rjlipton.wordpress.com/2009/06/09/computing-very-large-sums/
$\begingroup$
$\endgroup$
1
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).
answered May 12, 2015 at 3:04
-
$\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$– ParamarMay 12, 2015 at 13:19
$\begingroup$
$\endgroup$
2
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. ...
answered May 13, 2015 at 10:24
-
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$ May 13, 2015 at 14:57
-
$\begingroup$ @AndrásSalamon: good point!!! added it to the answer :-) $\endgroup$ May 13, 2015 at 15:05