<p>Jerrum, Valiant and Vazirani showed that if for a "self-reducible" NP-relation, there exists a polynomial time approximate counter which produces a $1 + O(n^{-\beta})$ approximation for some constant $\beta &gt; 0$, then this counter can be bootstrapped to make an an FPRAS for the counting problem.  As far as I know, all known #P-complete problems do correspond to "self-reducible" NP-relations, and hence the claim on Wikipedia.  However the exact claim that an approximate counter which produces a poly($n$) approximation for a self-reducible NP-relation can be bootstrapped to produce an FPRAS for counting was proved by Jerrum and Sinclair.  The citation I can think of the top of my head is <a href="http://dl.acm.org/citation.cfm?id=140552">Sinclair, 1993</a>. </p>

CC BY-SA 3.0
2011-10-09T18:19:51.510Z
2011-10-09T18:39:22.617Z
2011-10-09T18:39:22.617Z
Piyush
<p>The claim is not hard to see for specific problems though proving it for all #P-complete problems may require some more formalism. Suppose for some #P-complete problem one can obtain a $p(n)$-approximation. Given an instance $I$ make a new instance $I′$ which contains $k$ copies of $I$. The number of solutions to $I′$ is $a^k$ where $a$ is the number of solutions to $I$. Thus, choosing $k$ sufficiently large, even a polynomial-ratio approximation to $I&#39;$ can be used to approximate $a$ pretty well. </p>

CC BY-SA 3.0
2011-10-09T16:09:16.210Z
2011-10-09T16:09:16.210Z
Chandra Chekuri
<p>I just found the following sentence from the #P wiki page:</p>

<p>"Jerrum, Valiant, and Vazirani showed that every #P-complete problem either has an FPRAS, or is essentially impossible to approximate; if there is any polynomial-time algorithm which consistently produces an approximation of a #P-complete problem which is within a polynomial ratio in the size of the input of the exact answer, then that algorithm can be used to construct an FPRAS.[3]"</p>

<p><a href="http://en.wikipedia.org/wiki/Sharp-P-complete" rel="noreferrer">http://en.wikipedia.org/wiki/Sharp-P-complete</a></p>

<p>the referece [3] is 
Mark R. Jerrum; Leslie G. Valiant; Vijay V. Vazirani (1986). "Random Generation of Combinatorial Structures from a Uniform Distribution". Theoretical Computer Science (Elsevier) 32: 169–188.</p>

<p>I took a quick look at [3]. But it seems to me that the results of [3] do not contain anything similar to what is in the wiki page. Is there a mistake in the wiki page? Thanks.</p>

CC BY-SA 3.0
2011-10-08T14:18:57.747Z
How did you find that (journal) version of the paper?
Tyson Williams
CC BY-SA 3.0
2011-10-08T19:38:52.950Z
http://www.stat.duke.edu/~scs/Courses/Stat376/Papers/ConvergeRates/RandomizedAlgs/JerrumValiantVaziraniTCS1986.pdf
Suresh Venkat
CC BY-SA 3.0
2011-10-08T20:11:12.890Z
The claim is not hard to see for specific problems though proving it for all #P-complete problems may require some more formalism. Suppose for some #P-complete problem one can obtain a $p(n)$-approx. Given an instance $I$ make a new instance $I'$ which contains $k$ copies of $I$. The number of solutions to $I'$ is $a^k$ where $a$ is the # of solutions to $I$. Thus, choosing $k$ sufficiently large even a polynomial-ratio approx for $a^k$ can be used to approximate $a$ pretty well.
Chandra Chekuri
CC BY-SA 3.0
2011-10-09T06:50:14.077Z
@Chandra, post it as an answer? :)
Kaveh
<ds.algorithms><counting-complexity><randomized-algorithms>
FPRAS for #P-complete problems
jian
# FPRAS for #P-complete problems

(Asked by: username_0 on 2011-10-08)

I just found the following sentence from the #P wiki page:

"Jerrum, Valiant, and Vazirani showed that every #P-complete problem either has an FPRAS, or is essentially impossible to approximate; if there is any polynomial-time algorithm which consistently produces an approximation of a #P-complete problem which is within a polynomial ratio in the size of the input of the exact answer, then that algorithm can be used to construct an FPRAS.[3]"

<http://en.wikipedia.org/wiki/Sharp-P-complete>

the referece [3] is
Mark R. Jerrum; Leslie G. Valiant; Vijay V. Vazirani (1986). "Random Generation of Combinatorial Structures from a Uniform Distribution". Theoretical Computer Science (Elsevier) 32: 169–188.

I took a quick look at [3]. But it seems to me that the results of [3] do not contain anything similar to what is in the wiki page. Is there a mistake in the wiki page? Thanks.

**Tags:** ds.algorithms, counting-complexity, randomized-algorithms
> **Comments:**
> **username_1**: How did you find that (journal) version of the paper?  
> **username_2**: http://www.stat.duke.edu/~scs/Courses/Stat376/Papers/ConvergeRates/RandomizedAlgs/JerrumValiantVaziraniTCS1986.pdf  
> **username_3**: The claim is not hard to see for specific problems though proving it for all #P-complete problems may require some more formalism. Suppose for some #P-complete problem one can obtain a $p(n)$-approx. Given an instance $I$ make a new instance $I'$ which contains $k$ copies of $I$. The number of solutions to $I'$ is $a^k$ where $a$ is the # of solutions to $I$. Thus, choosing $k$ sufficiently large even a polynomial-ratio approx for $a^k$ can be used to approximate $a$ pretty well.  
> **username_4**: @Chandra, post it as an answer? :)  

---

## 2 answers

### Answer by username_3 on 2011-10-09. Score: 9 | Accepted answer

The claim is not hard to see for specific problems though proving it for all #P-complete problems may require some more formalism. Suppose for some #P-complete problem one can obtain a $p(n)$-approximation. Given an instance $I$ make a new instance $I′$ which contains $k$ copies of $I$. The number of solutions to $I′$ is $a^k$ where $a$ is the number of solutions to $I$. Thus, choosing $k$ sufficiently large, even a polynomial-ratio approximation to $I'$ can be used to approximate $a$ pretty well.


---

### Answer by username_5 on 2011-10-09. Score: 9

Jerrum, Valiant and Vazirani showed that if for a "self-reducible" NP-relation, there exists a polynomial time approximate counter which produces a $1 + O(n^{-\beta})$ approximation for some constant $\beta > 0$, then this counter can be bootstrapped to make an an FPRAS for the counting problem. As far as I know, all known #P-complete problems do correspond to "self-reducible" NP-relations, and hence the claim on Wikipedia. However the exact claim that an approximate counter which produces a poly($n$) approximation for a self-reducible NP-relation can be bootstrapped to produce an FPRAS for counting was proved by Jerrum and Sinclair. The citation I can think of the top of my head is [Sinclair, 1993](http://dl.acm.org/citation.cfm?id=140552).


---

