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?
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
