1
$\begingroup$

In the lecture notes Introduction to Complexity Theory by Goldreich, there is a section called "How close is $\#P$ is to $NP$". It is stated there that a $P^{NP}$ machine would approximate $\#P$ in random polynomial time. In fact I interpret this random approximation as a $FPRAS$ for any function in $\#P$.

Now in the seminal paper: M. Jerrum, A. Sinclair, and E. Vigoda, A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries (JACM version), on page 31, there is an binary search algorithm which takes an $FPRAS$ for the Permanent to a $BPP$ algorithm for the Permanent.

Taking both algorithms together, this suggest that one could exponential approximation with high probability the Permanent leading to $P^{NP} \ge \#P$.

This clearly cannot be right! So the question is what mistake have I made?

My apologies if this question is stupid.

$\endgroup$
  • 2
    $\begingroup$ Sorry, but I couldn't understand what you meant by "Taking both Algorithms together, this suggest that one could exponential approximation with high probability the Permanent leading to P^NP > = #P". Thus, I really suggest that you edit your question to make it clearer. In any case, both of these results you mentioned show that approximating counting can be done within the second level of the polytime hierarchy or so. On the other hand, #P is the class of exact counting, which is believed to be harder than approximate counting. So I believe your conclusion doesn't make sense. $\endgroup$ – Dai Le Dec 21 '10 at 12:39
  • 1
    $\begingroup$ Which version of the paper are you referring to? The JACM version has only 27 pages. In any case, the paper proves that Permanent (for matrices with nonnegative entries) has an FPRAS. It does not prove that it is possible to convert this FPRAS to a randomized polynomial-time algorithm for computing permanent exactly (which would imply BPP=PP and would be a huge result). $\endgroup$ – Tsuyoshi Ito Dec 21 '10 at 13:54
  • $\begingroup$ Thanks for all your communications! It appears that I will not be able to explain what I have in mind on this blog. In regarding to Dai Le, I was under the impression that exponential accurate counting approximations was equivalent to exact counting! Finally, regarding Tsuyoshi, I apologise about not providing a link: www.dcs.ed.ac.uk/home/mrj/PermanentRev.pdf. $\endgroup$ – Zelah 02 Dec 21 '10 at 14:49
  • 4
    $\begingroup$ Btw, this is not a blog. $\endgroup$ – Kaveh Dec 21 '10 at 16:43
5
$\begingroup$

I think you misunderstood the definition of $\mathsf{FPRAS}$.

Let $f: \Sigma^*\rightarrow Z^+$ be a function in $\#\mathsf{P}$. An algorithm $A$ is an $\mathsf{FPRAS}$ for $f$ if for each $x\in \Sigma^*$, and error parameter $\epsilon >0$, \begin{align*} Pr[|A(x)-f(x)] \le \epsilon f(x)] \ge 3/4 \end{align*} and the running time of $A$ is polynomial in $|x|$ and $1/\epsilon$.

So if you want to reduce the error to exponentially small, then the running time will also become exponential!

Note that both of the results you mentioned show that approximating counting can be done within the second level of the polytime hierarchy $\mathsf{PH}$ or so. On the other hand, $\#\mathsf{P}$ is the class of exact counting, which is widely believed to be harder than approximate counting. Otherwise, $\#\mathsf{P}$ is also contained in $\mathsf{FP}^\mathsf{NP}$, which implies that $\mathsf{PH}$ will collapse at least to the second level.

$\endgroup$
  • $\begingroup$ You appear to be claiming that if #P⊆PH then the polynomial hierarchy collapses to the second level, but why is that true? (Set aside the pedantic point that you probably meant PP instead of #P because #P is not a class of decision problems and therefore cannot be a subset of PH.) $\endgroup$ – Tsuyoshi Ito Dec 21 '10 at 19:08
  • $\begingroup$ Sorry, my bad! :-) What I meant is that if exact counting can be done in the second level of PH, then PP is in second level, then PH collapse to the second level. Thanks for your comment. $\endgroup$ – Dai Le Dec 21 '10 at 19:55

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.