JavaScript is disabled for your browser. Some features of this site may not work without it.
Exact Counting is as Easy as Approximate Counting

Author
Cai, Jin-yi; Hemachandra, Lane A.
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.
Date Issued
1986-06Publisher
Cornell University
Subject
computer science; technical report
Previously Published As
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR86-761
Type
technical report