<p>The answer to the question 2 is that the complexity of the counting problem #B can be basically anything (not even necessarily computable).  More precisely, the restriction that the decision version is in P does not have any implication on the complexity of the counting version.  This is because you can add a dummy solution to any relation problem so that the decision version becomes trivial (the answer becomes always yes) without changing the complexity of the counting version.</p>

CC BY-SA 2.5
2010-12-01T19:16:53.120Z
why do u say so?"(not even necessarily computable)" It is clear that if B is a decision problem in P then the #B is in #P, directly from the definition of class #P! but proving #B is also #P-com is important, and adding dummy solutions should not effect on the complexity of counting. you agree?
marjoonjan
CC BY-SA 2.5
2010-12-01T19:26:24.490Z
@marjoonjan: “It is clear that if B is a decision problem in P then the #B is in #P, directly from the definition of class #P” That is false.  Also, I get the impression that you believe that a decision problem B uniquely determines the counting problem #B, but it is not the case, as I explained in this answer.
Tsuyoshi Ito
CC BY-SA 2.5
2010-12-01T14:49:49.433Z
2010-12-01T14:49:49.433Z
Tsuyoshi Ito
<p>If you insist on parsimonious reductions (where the number of solutions is preserved) you cannot have such a reduction unless P = NP because the decision algorithm for non-emptyness of solutions for B will give you a decision algorithm for non-emptyness of solutions for A. On the other hand, if you allow other kind of reductions you can have such a case. For example, Valiant showed that #SAT reduces to the problem of counting perfect matchings in a bipartite graph: the reduction starts with a CNF-formula $F$ and builds a bipartite graph $G$ whose number of perfect matchings mod $2^{8m}+1$ is $4^m$ times the number of satisfying assignments of $F$, where $m$ is the number of literal occurrences in $F$. Note how this is not a parsimonious reduction, but a reduction nonetheless since you can recover the number of satisfying assignments of $F$ from the number of perfect matchings of $G$.</p>

<p>See Chapter 18 in Papadimitriou's "Computational Complexity" book for a clear exposition of this.</p>

CC BY-SA 2.5
2010-11-30T08:02:06.517Z
2010-11-30T08:02:06.517Z
slimton
<p>1) Is it possible to have a parsimonious reduction from a #P-complete problem #A to a counting problem #B when (the decision version) A is NP-complete and the B is in P?</p>

<p>For example, can there be a parsimonious reduction from #SAT to #B, when B is in P? </p>

<p>2) If B is in P, what are the different possibilities for the complexity of #B?</p>

<cc.complexity-theory><complexity-classes><counting-complexity>
#P-complete problem whose decision version is in P
marjoonjan
# #P-complete problem whose decision version is in P

(Asked by: username_0 on 2010-11-30)

1) Is it possible to have a parsimonious reduction from a #P-complete problem #A to a counting problem #B when (the decision version) A is NP-complete and the B is in P?

For example, can there be a parsimonious reduction from #SAT to #B, when B is in P?

2) If B is in P, what are the different possibilities for the complexity of #B?

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


---

## 2 answers

### Answer by username_2 on 2010-11-30. Score: 20 | Accepted answer

If you insist on parsimonious reductions (where the number of solutions is preserved) you cannot have such a reduction unless P = NP because the decision algorithm for non-emptyness of solutions for B will give you a decision algorithm for non-emptyness of solutions for A. On the other hand, if you allow other kind of reductions you can have such a case. For example, Valiant showed that #SAT reduces to the problem of counting perfect matchings in a bipartite graph: the reduction starts with a CNF-formula $F$ and builds a bipartite graph $G$ whose number of perfect matchings mod $2^{8m}+1$ is $4^m$ times the number of satisfying assignments of $F$, where $m$ is the number of literal occurrences in $F$. Note how this is not a parsimonious reduction, but a reduction nonetheless since you can recover the number of satisfying assignments of $F$ from the number of perfect matchings of $G$.

See Chapter 18 in Papadimitriou's "Computational Complexity" book for a clear exposition of this.


---

### Answer by username_1 on 2010-12-01. Score: 7

The answer to the question 2 is that the complexity of the counting problem #B can be basically anything (not even necessarily computable). More precisely, the restriction that the decision version is in P does not have any implication on the complexity of the counting version. This is because you can add a dummy solution to any relation problem so that the decision version becomes trivial (the answer becomes always yes) without changing the complexity of the counting version.

> **Comments:**
> **username_0**: why do u say so?"(not even necessarily computable)" It is clear that if B is a decision problem in P then the #B is in #P, directly from the definition of class #P! but proving #B is also #P-com is important, and adding dummy solutions should not effect on the complexity of counting. you agree?  
> **username_1**: @username_0: “It is clear that if B is a decision problem in P then the #B is in #P, directly from the definition of class #P” That is false.  Also, I get the impression that you believe that a decision problem B uniquely determines the counting problem #B, but it is not the case, as I explained in this answer.  

---

