<p>This is in PP.</p>

<p>Let $N$ be the size of the larger graph.  We will define a predicate $f(P, b)$ where $P$ is a permutation of the numbers from 1 to $N$ and $b$ is a single bit.</p>

<p>First, define a predicate $H(G, P)$ where $G$ is a graph (with nodes labeled from 1 to $n \leq N$) and $P$ is a permutation of the numbers from 1 to $N$.  Set $H$ to be true if and only if $P$ fixes the numbers from $n + 1$ to $N$ and if the permutation it induces of the numbers from 1 to $n$ defines a Hamiltonian cycle on $G$.  The number of $P$ for which $H(G, P)$ holds is then the number of Hamiltonian cycles in the graph.</p>

<p>Now, let $f(P, 0) = H(G_1, P)$ and $f(P, 1) = \overline{H(G_2, P)}$.  The number of $P, b$ pairs making $f$ 0 is then the number of Hamiltonian paths in $G_2$ plus the number of "Hamiltonian non-paths" in $G_1$, and vice versa holds for the number of pairs making $f$ 1.  Thus, whichever of these values is more common tells you which graph has more cycles, and this is precisely what PP allows you to do.</p>

CC BY-SA 3.0
2011-09-17T00:32:23.757Z
2011-09-17T00:32:23.757Z
Michael Cohen
<p>Define a decision problem H as follows. The input of H is a pair (G1,G2) of graphs, and the problem is to verify whether the number of Hamiltonian cycles in G1 is greater than the number of Hamiltonian cycles in G2. Is there a known complexity class C such that H is in C and H is C-hard under many-one reductions? Clearly H is in P^{#P}, and it is possible to prove that H is PP-hard under many-one reductions. But is H in PP? Or is H hard for the class P^{#P} under many-one reductions?</p>

<counting-complexity><hamiltonian-paths>
A decision problem related to the problem of counting Hamiltonian cycles
Marcelo
# A decision problem related to the problem of counting Hamiltonian cycles

(Asked by: username_0 on 2011-09-16)

Define a decision problem H as follows. The input of H is a pair (G1,G2) of graphs, and the problem is to verify whether the number of Hamiltonian cycles in G1 is greater than the number of Hamiltonian cycles in G2. Is there a known complexity class C such that H is in C and H is C-hard under many-one reductions? Clearly H is in P^{#P}, and it is possible to prove that H is PP-hard under many-one reductions. But is H in PP? Or is H hard for the class P^{#P} under many-one reductions?

**Tags:** counting-complexity, hamiltonian-paths


---

## 1 answers

### Answer by username_1 on 2011-09-17. Score: 8

This is in PP.

Let $N$ be the size of the larger graph. We will define a predicate $f(P, b)$ where $P$ is a permutation of the numbers from 1 to $N$ and $b$ is a single bit.

First, define a predicate $H(G, P)$ where $G$ is a graph (with nodes labeled from 1 to $n \leq N$) and $P$ is a permutation of the numbers from 1 to $N$. Set $H$ to be true if and only if $P$ fixes the numbers from $n + 1$ to $N$ and if the permutation it induces of the numbers from 1 to $n$ defines a Hamiltonian cycle on $G$. The number of $P$ for which $H(G, P)$ holds is then the number of Hamiltonian cycles in the graph.

Now, let $f(P, 0) = H(G\_1, P)$ and $f(P, 1) = \overline{H(G\_2, P)}$. The number of $P, b$ pairs making $f$ 0 is then the number of Hamiltonian paths in $G\_2$ plus the number of "Hamiltonian non-paths" in $G\_1$, and vice versa holds for the number of pairs making $f$ 1. Thus, whichever of these values is more common tells you which graph has more cycles, and this is precisely what PP allows you to do.


---

