0
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.