3
$\begingroup$

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?

$\endgroup$
8
$\begingroup$

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.

$\endgroup$

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.