# #P-complete problems are at least as hard as NP-complete problems

• 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?

• The statement means: "You can efficiently transform the inputs and use an algorithm $A$ that solves a #P-complete problem to solve an NPC problem $B$", i.e. $B \leq SAT \leq \#SAT \leq A$ (the time complexity is the same up to a polynomial overhead due to the first and third reductions, because the second one is simply a zero test). So $A$ cannot be easier than $B$ because it is itself a solver for $B$; i.e. as written by Valiant "$A$ is at least as hard as $B$". – Marzio De Biasi Aug 30 '14 at 9:59
• Possibly, you are only acquainted with the concept of (polynomial) many-to-one reductions in which case comparing classes of languages and functions by reduction seems odd. If that is indeed the case then you should look up Turing reductions and the idea of oracles. With these concepts the mentioned reductions seem quite natural – John D. Aug 30 '14 at 11:59

• When we talk about the decision version of a counting problem, we mean: Is there any solution at all, right? What if we instead ask: Is there a solution set containing $k$ different solutions? Do we then have #P-completeness iff NP-completeness? – Oliver Witt Sep 1 '14 at 10:40
• @OliverWitt Yes, by the decision version of a counting problem, I mean the problem "Is the answer to the counting problem nonzero?" The question "Is the answer to the counting problem at least $k$?" can be harder than this. For example, consider the following problem: the input is a Boolean formula $\varphi$ with $r$ variables and the output is the number of satisfying assignments to the formula $\varphi\vee (x_1\wedge\dots\wedge x_r)$. The decision version is easy (the answer is "yes"); the question "is the answer at least 2?" is NP-complete. – David Richerby Sep 1 '14 at 14:02
• Yes, but again: Is it true that "How many solutions are there to problem $A$?" is #P-complete if and only if the question "Are there at least $k$ solutions to problem $A$?" is NP-complete? At least the one direction is quite easy: If I can tell how many solutions there are, I can of course answer the question whether there are at least $k$. However, if I can answer the question if there are at least $k$ solutions, how do I infer from that the exact number of solutions? – Oliver Witt Sep 1 '14 at 19:02