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, 2016 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, 2016 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, 2016 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, 2016 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, 2016 at 3:01

1 Answer 1

Reset to default
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$
13
  • 2
    $\begingroup$ Okay. Now I'm confused. Doesn't $K_4$ have three Hamiltonian cycles? $\endgroup$
    – Peter Shor
    Feb 14, 2016 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, 2016 at 2:22
  • 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, 2016 at 18:33
  • 1
    $\begingroup$ @Turbo I believe it is still open; they just posted a paper that discusses this and related issues arxiv.org/abs/2204.13149 $\endgroup$
    – Joshua Grochow
    May 11 at 14:38
  • 1
    $\begingroup$ @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. $\endgroup$
    – Joshua Grochow
    May 11 at 21:44

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.