# FPRAS for #P-complete problems

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.

• How did you find that (journal) version of the paper? Oct 8 '11 at 14:18
• stat.duke.edu/~scs/Courses/Stat376/Papers/ConvergeRates/… Oct 8 '11 at 19:38
• 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. Oct 8 '11 at 20:11
• @Chandra, post it as an answer? :) Oct 9 '11 at 6:50

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.

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.