Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
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$.
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.
