Cai, Jin-yiHemachandra, Lane A.2007-04-232007-04-231986-06http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR86-761https://hdl.handle.net/1813/6601We 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.751350 bytes231687 bytesapplication/pdfapplication/postscripten-UScomputer sciencetechnical reporttechnical report