<p>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."</p>

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

CC BY-SA 3.0
2014-08-31T09:37:23.650Z
Thanks, that clarified it. My mistake was to assume they were saying that the decision version of a problem is at least NP-complete if the counting version is #P-complete.
Oliver Witt
CC BY-SA 3.0
2014-08-31T09:52:40.230Z
Yeah, your example of counting matchings shows that can't be the case. Also, note that even the converse isn't a theorem: because of the different notions of reduction (many-one for **NP**, polytime Turing for **#P**), it's not actually known that the decision problem being **NP**-complete implies that the counting problem is **#P**-complete. On the other hand, there are no known counterexamples and I don't think anyone believes there are any.
David Richerby
CC BY-SA 3.0
2014-09-01T10:40:31.450Z
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
CC BY-SA 3.0
2014-09-01T14:02:01.697Z
@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
CC BY-SA 3.0
2014-09-01T19:02:05.037Z
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
CC BY-SA 3.0
2014-09-01T19:11:11.430Z
I guess it depends on what kind of reductions you are using again. When using Turing reductions or oracles, then the second direction becomes clear, too.
Oliver Witt
CC BY-SA 3.0
2014-09-01T20:57:27.657Z
@OliverWitt Let $\#A$ be the counting problem "How many solutions does $A$ have?" and let $\#A>k$? be the decision problem "Does $\#A$ have $>k$ solutions?" To show that $\#A$ is **#P**-complete, you have to show how to polytime Turing reduce every problem in **#P** to it; to show that $\#A>k$? is **NP**-complete, you have to show how to reduce every problem in **NP** to it with, e.g., logspace many-one reductions. Reducing in either direction between $\#A$ and $\#A>k$? doesn't achieve (or even, as far as I can see, help with) either of those goals.
David Richerby
CC BY-SA 3.0
2014-09-01T20:58:41.537Z
@OliverWitt But I don't know if $\#A$ is **#P**-complete iff $\#A>k$? is **NP**-complete.
David Richerby
CC BY-SA 3.0
2014-08-30T10:07:50.173Z
2014-08-30T10:07:50.173Z
David Richerby
<p>I just read</p>

<ul>
<li>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)</li>
</ul>

<p>and one of the first sentences is</p>

<blockquote>
  <p>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.</p>
</blockquote>

<p>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:</p>

<p><a href="http://en.wikipedia.org/wiki/Sharp-P-complete" rel="nofollow">http://en.wikipedia.org/wiki/Sharp-P-complete</a></p>

<p>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?</p>

CC BY-SA 3.0
2014-08-30T09:59:55.573Z
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
CC BY-SA 3.0
2014-08-30T11:59:58.207Z
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.
<cc.complexity-theory><complexity-classes><counting-complexity>
#P-complete problems are at least as hard as NP-complete problems
Oliver Witt
# #P-complete problems are at least as hard as NP-complete problems

(Asked by: username_0 on 2014-08-30)

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?

**Tags:** cc.complexity-theory, complexity-classes, counting-complexity

> **Comments:**
> **username_1**: 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$".  
> **username_2**: 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  

---

## 1 answers

### Answer by username_3 on 2014-08-30. Score: 6 | Accepted answer

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 B, I could also solve 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.

> **Comments:**
> **username_0**: Thanks, that clarified it. My mistake was to assume they were saying that the decision version of a problem is at least NP-complete if the counting version is #P-complete.  
> **username_3**: Yeah, your example of counting matchings shows that can't be the case. Also, note that even the converse isn't a theorem: because of the different notions of reduction (many-one for **NP**, polytime Turing for **#P**), it's not actually known that the decision problem being **NP**-complete implies that the counting problem is **#P**-complete. On the other hand, there are no known counterexamples and I don't think anyone believes there are any.  
> **username_0**: 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?  
> **username_3**: @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.  
> **username_0**: 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?  
> **username_0**: I guess it depends on what kind of reductions you are using again. When using Turing reductions or oracles, then the second direction becomes clear, too.  
> **username_3**: @OliverWitt Let $\#A$ be the counting problem "How many solutions does $A$ have?" and let $\#A>k$? be the decision problem "Does $\#A$ have $>k$ solutions?" To show that $\#A$ is **#P**-complete, you have to show how to polytime Turing reduce every problem in **#P** to it; to show that $\#A>k$? is **NP**-complete, you have to show how to reduce every problem in **NP** to it with, e.g., logspace many-one reductions. Reducing in either direction between $\#A$ and $\#A>k$? doesn't achieve (or even, as far as I can see, help with) either of those goals.  
> **username_3**: @OliverWitt But I don't know if $\#A$ is **#P**-complete iff $\#A>k$? is **NP**-complete.  

---

