# Complexity of counting when there is no parsimonious reduction

Let $\#A$ be a counting problem in $FP$ and let $\#B$ a counting problem with unknown complexity. Suppose there is a polynomial-time, one-to-many reduction from $B$ to $A$, but there is no specific relation between the solutions of $A$ and those of $B$.

For example, $i$ solutions of $A$ could be related to one solution of $B$, and $j$ other solutions of $A$ could be related to a different solution of $B$ and so on. I only know that I can cover all solutions of $B$ via the reduction, and nothing more about solutions of $B$.

Is it possible to conclude that $\#B$ is in $FP$? Or do I have to find a strict parsimonious reduction or weak parsimonious reduction in a way that I could obtain the exact number of solutions of $B$ (possibly with help from the reduction)?

## 1 Answer

I don't think that having a non-parsimonious reduction helps in proving that a counting problem is in FP. Eg. if either 1 or 2 instances are mapped to 1, and which of these depends on something NP-hard, then you do not know anything about the complexity of your problem. Of course, you might have a special reduction from which you get some extra information.