Division by two of functions in #P

Question

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.

I don't even see an answer for the cases in which Range(F) = {0,1,2} . — , Jan 05 '16 at 10:58
@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, Jan 05 '16 at 13:15
@RickyDemer: Do you see the answer when Range(F) is just {0,1}? — Joshua Grochow, Jan 05 '16 at 17:08
@JoshuaGrochow : Yes, it's "Accept if and only if you guessed both 2F witnesses in lexicographic order". — , Jan 05 '16 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}$ — Tayfun Pay, Jan 06 '16 at 03:28
@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, Jan 06 '16 at 05:01
@TayfunPay : There's presumably a typo, since you gave the definition of NP. — , Jan 06 '16 at 09:58
How hard is it to tell whether a function in #PP is always even? I expect it's undecidable. — Peter Shor, Jan 06 '16 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. — , Feb 14 '16 at 03:01

domotorp · Answer 1 · 2016-02-14T02:25:16.267

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

edited Feb 14 '16 at 02:25

answered Jan 07 '16 at 21:28

domotorp

13,931
37
93

2

Okay. Now I'm confused. Doesn't $K_4$ have three Hamiltonian cycles? – Peter Shor Feb 14 '16 at 02:17
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? – Peter Shor Feb 14 '16 at 02:22
Indeed, funny that no one noticed earlier... I've added it. – domotorp Feb 14 '16 at 02:26
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 Feb 14 '16 at 06:39
@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 Feb 14 '16 at 08:55
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 Feb 14 '16 at 13:30
@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 Feb 15 '16 at 15:48
@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 Feb 15 '16 at 20:27
@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 Feb 15 '16 at 21:43
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). – Emil Jeřábek Feb 17 '16 at 18:33
@JoshuaGrochow Do you know if the answer to Igor Pak's question is YES? – Turbo May 06 '22 at 18:36
1

@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 May 11 '22 at 14:38
1

@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 May 11 '22 at 21:44

Division by two of functions in #P

1 Answers1