<p>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.</p>

CC BY-SA 3.0
2011-04-17T12:49:35.100Z
2011-04-17T12:49:35.100Z
domotorp
<p>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$.</p>

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

<p>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)?</p>

<cc.complexity-theory><complexity-classes><counting-complexity>
Complexity of counting when there is no parsimonious reduction
marjoonjan
# Complexity of counting when there is no parsimonious reduction

(Asked by: username_0 on 2011-04-16)

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

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

---

## 1 answers

### Answer by username_1 on 2011-04-17. Score: 3

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.


---

