Exact Counting is as Easy as Approximate Counting
| dc.contributor.author | Cai, Jin-yi | en_US |
| dc.contributor.author | Hemachandra, Lane A. | en_US |
| dc.date.accessioned | 2007-04-23T17:14:53Z | |
| dc.date.available | 2007-04-23T17:14:53Z | |
| dc.date.issued | 1986-06 | en_US |
| dc.description.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. | en_US |
| dc.format.extent | 751350 bytes | |
| dc.format.extent | 231687 bytes | |
| dc.format.mimetype | application/pdf | |
| dc.format.mimetype | application/postscript | |
| dc.identifier.citation | http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR86-761 | en_US |
| dc.identifier.uri | https://hdl.handle.net/1813/6601 | |
| dc.language.iso | en_US | en_US |
| dc.publisher | Cornell University | en_US |
| dc.subject | computer science | en_US |
| dc.subject | technical report | en_US |
| dc.title | Exact Counting is as Easy as Approximate Counting | en_US |
| dc.type | technical report | en_US |