#P-complete problems are at least as hard as NP-complete problems 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?
It's not at all weird to compare the complexity of counting and decision problems: reductions allow you to do that very naturally. You can use reductions to compare any kind of problem: decision, counting, approximate counting, optimization, function problems, ... All of this follows from the intuitive notion that a reduction from A to B means "If I could solve&nbsp;B, I could also solve&nbsp;A at roughly the same cost."

The existence of easy decision problems whose counting version is hard is a red herring. Counting matchings is the hard problem: if you could do that, you could solve any NP problem by reduction. Detecting matchings is easy: you can do that but it doesn't (seem to) help you to solve NP-complete problems.