I just read
- J. Scott Provan, Michael O. Ball: The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected. SIAM J. Comput. 12(4): 777-788 (1983)
and one of the first sentences is
Valiant defines the notion of the #P-complete class (...) and shows that problems in this class are at least as hard as NP-complete problems.
My first problem is that is seems weird to directly compare the complexity of counting and decision problems. But more importantly: There are quite easy decision problems, whose counting variant is #P-complete, for example satisfiability of boolean formulas in DNF. This can also be read on Wikipedia:
http://en.wikipedia.org/wiki/Sharp-P-complete
So is the statement, that a #P-complete problem is at least as hard as a NP-complete problem simply wrong or am I getting something wrong?