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

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$.