# Division by two of functions in #P

Let $F$ be an integer valued function such that $2F$ is in $\#P$. Does it follow that $F$ is in $\#P$? Are there reasons to believe this is unlikely to always hold? Any references I should know about?

Somewhat surprisingly, this situation came up (with a much larger constant), for a function $F$ for which $F \in? \#P$ is an old open problem.

Note: I am aware of the paper M. Ogiwara, L. Hemachandra, A complexity theory for feasible closure properties where a related division-by-2 problem has been studied (see Thm 3.13). Their problem is different however, as they define the division for all functions via the floor operator. That allowed them to make some quick reductions to parity problems.

• @Kaveh: If $f(x)$ is a $\#P$ function, and $g(y)$ a poly-time function, then $f(g(y))$ is in $\#P$, but $g(f(x))$ not necessarily (presumably). For example, there seems to be no reason why all nonnegative GapP functions should be in $\#P$, but they are reducible to $\#P$ in this way. Jan 5, 2016 at 13:15
• @JoshuaGrochow : ​ Yes, it's "Accept if and only if you guessed both 2F witnesses in lexicographic order". ​ ​ ​ ​
– user6973
Jan 5, 2016 at 21:39
• @JoshuaGrochow If you do division with NO floor function then ${\bf PP}$ collapses to the following complexity class, which I just defined, via Theorem 5.9 on TCTC book. ${\bf UPPX} = \{ L |$ there is a polynomial-time predicate P and a polynomial q such that, for all $x$, $\bf 1.$ $x \not \in L \Rightarrow ||\{y|$ $|y|\leq q(|x|) \wedge P(x,y)\}|| < 1$ $\bf 2.$ $x \in L \Rightarrow ||\{y|$ $|y|\leq q(|x|) \wedge P(x,y)\}|| \geq 1$$\}$ Then one needs to show where ${\bf UPPX}$ belongs in the complexity hierarchy. It is hopefully the case that ${\bf UPPX} = {\bf PP}$ Jan 6, 2016 at 3:28
• How hard is it to tell whether a function in #PP is always even? I expect it's undecidable. Jan 6, 2016 at 16:05
• @PeterShor : ​ ​ ​ That's certainly undecidable. ​ One can take a machine that accepts if and only if the counting witness is all 1s and the same length as the input and M halts in exactly [that length] steps. ​ ​ ​ ​ ​ ​ ​ ​
– user6973
Feb 14, 2016 at 3:01

## 1 Answer

I try to give my intuition why I think this is unlikely to hold. Take your favorite problem in $PPA$, and convert it into a problem in $\sharp P$, e.g., our function $f$ can be the number of Hamiltonian cycles in an input 3-regular graph containing a certain fixed edge. From the parity argument we know that $f$ is always even, so you can define $F:=f/2$ and I see no reason why $F$ would be in $\sharp P$.

• Okay. Now I'm confused. Doesn't $K_4$ have three Hamiltonian cycles? Feb 14, 2016 at 2:17
• Okay ... I've checked. The theorem is that every edge appears in an even number of (undirected) Hamiltonian cycles in a 3-regular graph, not that there are an even number of Hamiltonian cycles total. So the right counting problem is: given a three-regular graph and an edge $e$, let $f$ be the number of Hamiltonian cycles in $G$ that go through $e$. Is $F/2$ in #P? Feb 14, 2016 at 2:22
• The fact is not true. For instance, it is easy to check that it fails for all connected 3-regular graphs on 8 vertices (see en.wikipedia.org/wiki/Table_of_simple_cubic_graphs#8_nodes for a list), except for the cube (which is edge-transitive). Feb 17, 2016 at 18:33
• @Turbo I believe it is still open; they just posted a paper that discusses this and related issues arxiv.org/abs/2204.13149 May 11 at 14:38
• @Turbo I believe their Proposition 7.5.5 gives an oracle separation; that is, a function F such that 2F is in #P^A but F is not. May 11 at 21:44