19
$\begingroup$

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.

Improve this question
$\endgroup$
11
  • 3
    $\begingroup$ @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. $\endgroup$
    – Emil Jeřábek
    Jan 5 '16 at 13:15
  • 1
    $\begingroup$ @JoshuaGrochow : ​ Yes, it's "Accept if and only if you guessed both 2F witnesses in lexicographic order". ​ ​ ​ ​ $\endgroup$
    – user6973
    Jan 5 '16 at 21:39
  • 1
    $\begingroup$ @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}$ $\endgroup$
    – Tayfun Pay
    Jan 6 '16 at 3:28
  • 2
    $\begingroup$ How hard is it to tell whether a function in #PP is always even? I expect it's undecidable. $\endgroup$
    – Peter Shor
    Jan 6 '16 at 16:05
  • 2
    $\begingroup$ @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. ​ ​ ​ ​ ​ ​ ​ ​ $\endgroup$
    – user6973
    Feb 14 '16 at 3:01
4
$\begingroup$

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

Improve this answer
$\endgroup$
10
  • 2
    $\begingroup$ Okay. Now I'm confused. Doesn't $K_4$ have three Hamiltonian cycles? $\endgroup$
    – Peter Shor
    Feb 14 '16 at 2:17
  • 5
    $\begingroup$ 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? $\endgroup$
    – Peter Shor
    Feb 14 '16 at 2:22
  • $\begingroup$ Indeed, funny that no one noticed earlier... I've added it. $\endgroup$
    – domotorp
    Feb 14 '16 at 2:26
  • $\begingroup$ 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... $\endgroup$
    – Joshua Grochow
    Feb 14 '16 at 6:39
  • 2
    $\begingroup$ 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). $\endgroup$
    – Emil Jeřábek
    Feb 17 '16 at 18:33

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.