#P-complete problem whose decision version is in 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?

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?

2 Answers

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.

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.

• 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? Dec 1 '10 at 19:16
• @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. Dec 1 '10 at 19:26