# Is Permanent $+$-reducible?

Suppose we have two bipartite graphs $G_1$ and $G_2$ with perfect matching count $P_1$ and $P_2$ respectively then their disjoint union gives a bipartite graph with perfect matching $P_1P_2$.

Is there a graph construction in polynomial time to get a bipartite graph from $G_1$ and $G_2$ with perfect matching count $P_1+P_2$ without knowing $P_1$ but knowing $P_2$?

• FYI, #P closure under addition means given $f,g \in \mathsf{\# P}$, $f+g$ is in $\mathsf{\# P}$ - this is the sum of two different functions on the same input. You are asking about addition of the same function on two different inputs.... – Joshua Grochow Aug 9 '17 at 20:33
• What do you mean by "the decision version" of a #P problem? Its graph? Subgraph? Bitgraph? Something else? – Emil Jeřábek supports Monica Aug 9 '17 at 20:58
• @777: I wasn't asking, I was stating a result. You can get a permanent back (with perhaps multiplying $P_1 + P_2$ by some power of 2) using Valiant's $\mathsf{\# P}$-completeness of perm. – Joshua Grochow Aug 10 '17 at 2:17
• Okay. That wasn't the point of my original comment, though. My point was: it's not just that you don't want the power of 2; you are asking a different type of question. Instead of asking for the sum of two functions of the same input, you are asking for the sum of one function over two different inputs. – Joshua Grochow Aug 10 '17 at 4:13
• @777 The function $f$ counts the number of accepting paths of the machine on what input? – Sasho Nikolov Aug 10 '17 at 7:25