6
$\begingroup$

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.

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

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.

$\endgroup$
7
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.