Exact Counting is as Easy as Approximate Counting

Abstract

We show that exact counting and approximate counting are polynomially equivalent. That is $P^{#P} = P^{Approx#P}$, where #$P$ is a function that computes the number of solutions to a given Boolean formula $f$ (denoted by $|| f ||$), and Approx#P computes a short list that contains $|| f ||$. It follows that if there is a good polynomial time approximator for #$P$ (i.e., one where the list has at most $O(|f|^{1-\epsilon})$ elements), then $P = NP = P^{#P}$ and probabilistic polynomial time equals polynomial time. Thus we have strong evidence that #$P$ cannot be easily approximated.