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

CC BY-SA 3.0
2016-02-14T02:17:54.677Z
Okay. Now I'm confused. Doesn't $K_4$ have three Hamiltonian cycles?
Peter Shor 
CC BY-SA 3.0
2016-02-14T02:22:24.040Z
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?
Peter Shor 
CC BY-SA 3.0
2016-02-14T02:26:05.710Z
Indeed, funny that no one noticed earlier... I've added it.
domotorp
CC BY-SA 3.0
2016-02-14T06:39:39.647Z
Although generally I agree with your intuition, in this case, I think $f/2$ may actually be in #P: Let e=(v_1,v_2) be the edge in G. Let u,w be the neighbors of v_1 that aren't v_2. The following NP machine has f/2 accepting paths: guess a Hamilton cycle that includes the pair of edges (u,v_1) and (v_1,v_2). (The point is that the proof of even parity creates a bijection between such Ham. cycles and those that includes (w,v_1) and (v_1,v_2).) So for the intuition to work you need something in PPA that goes via e.g. a counting argument, or that avoids some easy bijection...
Joshua Grochow
CC BY-SA 3.0
2016-02-14T08:55:41.977Z
@Joshua After Peter's comment, I've also checked the proof fearing that the situation might be what you write, but I don't think it is. Maybe there are different proofs? Could you link to the one you are referring to? I am just following the one that's on page 501, figure 1 here: https://www.cs.berkeley.edu/~christos/papers/On%20the%20Complexity.pdf
domotorp
CC BY-SA 3.0
2016-02-14T13:30:15.577Z
In fact, your claim would imply that the number of H cycles is the same through any edge of the graph, which is probably not true, though now I cannot find a counterexample.
domotorp
CC BY-SA 3.0
2016-02-15T15:48:23.570Z
@domotorp: (1) p. 641 here: http://www.sciencedirect.com/science/article/pii/S0022000098916117. (2) How does my claim imply that the number of cycles is the same through any edge? I agree that the latter fact is probably not true. Perhaps we should continue this in chat and then come back with the answer?
Joshua Grochow
CC BY-SA 3.0
2016-02-15T20:27:32.893Z
@Joshua (1) I couldn't find any mention of your claim there. (2) If there are $2k$ H cycles through an edge, then there are $k$ H cycles through the edge and any of its neighboring edges. But then there are also $2k$ H cycles through this neighboring edge etc. we are done using connectivity.
domotorp
CC BY-SA 3.0
2016-02-15T21:43:52.130Z
@domotorp: I agree with your reasoning in (2). (1) is not stated explicitly there, but I *thought* follows from the proof on p. 641. However, I agree that it seems unlikely that there is always the same number of Ham. cycles through every edge. I will have to think about this some more to see whether I've made a mistake, or if this seemingly unlikely fact is actually the case.
Joshua Grochow
CC BY-SA 3.0
2016-02-17T18:33:05.490Z
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 https://en.wikipedia.org/wiki/Table_of_simple_cubic_graphs#8_nodes for a list), except for the cube (which is edge-transitive).
Emil Jeřábek
CC BY-SA 4.0
2022-05-06T18:36:18.783Z
@JoshuaGrochow Do you know if the answer to Igor Pak's question is YES?
Turbo
CC BY-SA 4.0
2022-05-11T14:38:06.787Z
@Turbo I believe it is still open; they just posted a paper that discusses this and related issues https://arxiv.org/abs/2204.13149
Joshua Grochow
CC BY-SA 4.0
2022-05-11T21:44:28.337Z
@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.
Joshua Grochow
CC BY-SA 3.0
2016-01-07T21:28:42.827Z
2016-02-14T02:25:16.267Z
2016-02-14T02:25:16.267Z
domotorp
<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?</p>

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

<p><strong>Note:</strong> I am aware of the paper M. Ogiwara, L. Hemachandra, <a href="http://www.sciencedirect.com/science/article/pii/002200009390006I">A complexity theory for feasible closure properties</a> 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 <em>all</em> functions via the floor operator.  That allowed them to make some quick reductions to parity problems.  </p>

CC BY-SA 3.0
2016-01-05T11:54:28.597Z
Isn't #P closed under polynomial-time reductions?
Kaveh
CC BY-SA 3.0
2016-01-05T13:15:28.983Z
@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.
Emil Jeřábek
CC BY-SA 3.0
2016-01-05T17:08:47.457Z
@RickyDemer: Do you see the answer when Range(F) is just {0,1}?
Joshua Grochow
CC BY-SA 3.0
2016-01-05T21:49:18.993Z
@RickyDemer: Oh right. Duh :).
Joshua Grochow
CC BY-SA 3.0
2016-01-06T03:28:36.927Z
@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}$
Tayfun Pay
CC BY-SA 3.0
2016-01-06T05:01:06.210Z
@TayfunPay: For the question at hand, you need to not just consider "division with no rounding" but "division by 2 under the assumption that the number being divided is even."
Joshua Grochow
CC BY-SA 3.0
2016-01-06T16:05:39.723Z
How hard is it to tell whether a function in #PP is always even? I expect it's undecidable.
Peter Shor 
<cc.complexity-theory><complexity-classes><counting-complexity>
Division by two of functions in #P
Igor Pak
# Division by two of functions in #P

(Asked by: username_0 on 2016-01-05)

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](http://www.sciencedirect.com/science/article/pii/002200009390006I) 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.

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

> **Comments:**
> **username_1**: Isn't #P closed under polynomial-time reductions?  
> **username_2**: @username_1: 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.  
> **username_3**: @RickyDemer: Do you see the answer when Range(F) is just {0,1}?  
> **username_3**: @RickyDemer: Oh right. Duh :).  
> **username_4**: @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}$  
> **username_3**: @TayfunPay: For the question at hand, you need to not just consider "division with no rounding" but "division by 2 under the assumption that the number being divided is even."  
> **username_5**: How hard is it to tell whether a function in #PP is always even? I expect it's undecidable.  

---

## 1 answers

### Answer by username_6 on 2016-01-07. Score: 4

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

> **Comments:**
> **username_5**: Okay. Now I'm confused. Doesn't $K_4$ have three Hamiltonian cycles?  
> **username_5**: 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?  
> **username_6**: Indeed, funny that no one noticed earlier... I've added it.  
> **username_3**: Although generally I agree with your intuition, in this case, I think $f/2$ may actually be in #P: Let e=(v_1,v_2) be the edge in G. Let u,w be the neighbors of v_1 that aren't v_2. The following NP machine has f/2 accepting paths: guess a Hamilton cycle that includes the pair of edges (u,v_1) and (v_1,v_2). (The point is that the proof of even parity creates a bijection between such Ham. cycles and those that includes (w,v_1) and (v_1,v_2).) So for the intuition to work you need something in PPA that goes via e.g. a counting argument, or that avoids some easy bijection...  
> **username_6**: @Joshua After Peter's comment, I've also checked the proof fearing that the situation might be what you write, but I don't think it is. Maybe there are different proofs? Could you link to the one you are referring to? I am just following the one that's on page 501, figure 1 here: https://www.cs.berkeley.edu/~christos/papers/On%20the%20Complexity.pdf  
> **username_6**: In fact, your claim would imply that the number of H cycles is the same through any edge of the graph, which is probably not true, though now I cannot find a counterexample.  
> **username_3**: @username_6: (1) p. 641 here: http://www.sciencedirect.com/science/article/pii/S0022000098916117. (2) How does my claim imply that the number of cycles is the same through any edge? I agree that the latter fact is probably not true. Perhaps we should continue this in chat and then come back with the answer?  
> **username_6**: @Joshua (1) I couldn't find any mention of your claim there. (2) If there are $2k$ H cycles through an edge, then there are $k$ H cycles through the edge and any of its neighboring edges. But then there are also $2k$ H cycles through this neighboring edge etc. we are done using connectivity.  
> **username_3**: @username_6: I agree with your reasoning in (2). (1) is not stated explicitly there, but I *thought* follows from the proof on p. 641. However, I agree that it seems unlikely that there is always the same number of Ham. cycles through every edge. I will have to think about this some more to see whether I've made a mistake, or if this seemingly unlikely fact is actually the case.  
> **username_2**: 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 https://en.wikipedia.org/wiki/Table_of_simple_cubic_graphs#8_nodes for a list), except for the cube (which is edge-transitive).  
> **username_7**: @JoshuaGrochow Do you know if the answer to username_0's question is YES?  
> **username_3**: @username_7 I believe it is still open; they just posted a paper that discusses this and related issues https://arxiv.org/abs/2204.13149  
> **username_3**: @username_7 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.  

---

