Cornell University
Library
Cornell UniversityLibrary

eCommons

Help
Log In(current)
  1. Home
  2. Cornell Computing and Information Science
  3. Computer Science
  4. Computer Science Technical Reports
  5. Exact Counting is as Easy as Approximate Counting

Exact Counting is as Easy as Approximate Counting

File(s)
86-761.pdf (733.74 KB)
86-761.ps (226.26 KB)
Permanent Link(s)
https://hdl.handle.net/1813/6601
Collections
Computer Science Technical Reports
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-06
Publisher
Cornell University
Keywords
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

Site Statistics | Help

About eCommons | Policies | Terms of use | Contact Us

copyright © 2002-2026 Cornell University Library | Privacy | Web Accessibility Assistance