<p>I think you misunderstood the definition of $\mathsf{FPRAS}$. </p>

<blockquote>
  <p>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 &gt;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$.</p>
</blockquote>

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

<p>Note that both of the results you mentioned show that <em>approximating counting</em> 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 <em>exact counting</em>, 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.</p>

CC BY-SA 2.5
2010-12-21T19:08:15.940Z
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.)
Tsuyoshi Ito
CC BY-SA 2.5
2010-12-21T19:55:01.713Z
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.
Dai Le
CC BY-SA 2.5
2010-12-21T18:06:01.997Z
2010-12-21T19:57:09.433Z
2010-12-21T19:57:09.433Z
Dai Le
<p>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 <em>any</em> function in $\#P$.</p>

<p>Now in the seminal paper: M. Jerrum, A. Sinclair, and E. Vigoda, <a href="http://www.dcs.ed.ac.uk/home/mrj/PermanentRev.pdf" rel="nofollow">A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries</a> (<a href="http://dx.doi.org/10.1145/1008731.1008738" rel="nofollow">JACM version</a>), on page 31, there is an binary search algorithm which takes an $FPRAS$ for the Permanent to a $BPP$ algorithm for the Permanent.</p>

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

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

<p>My apologies if this question is stupid.</p>

CC BY-SA 2.5
2010-12-21T12:39:53.903Z
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.
Dai Le
CC BY-SA 2.5
2010-12-21T13:54:23.277Z
Which version of the paper are you referring to?  The [JACM version](http://dx.doi.org/10.1145/1008731.1008738) 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).
Tsuyoshi Ito
CC BY-SA 2.5
2010-12-21T14:49:21.777Z
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.
Zelah 02
CC BY-SA 2.5
2010-12-21T16:43:57.750Z
Btw, this is not a blog.
Kaveh
<cc.complexity-theory><complexity-classes><counting-complexity><permanent>
The Relationship between P^NP and the Permanent
Zelah 02
# The Relationship between P^NP and the Permanent

(Asked by: username_0 on 2010-12-21)

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](http://www.dcs.ed.ac.uk/home/mrj/PermanentRev.pdf) ([JACM version](http://dx.doi.org/10.1145/1008731.1008738)), 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.

**Tags:** cc.complexity-theory, complexity-classes, counting-complexity, permanent
> **Comments:**
> **username_1**: 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.  
> **username_2**: Which version of the paper are you referring to?  The [JACM version](http://dx.doi.org/10.1145/1008731.1008738) 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).  
> **username_0**: 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.  
> **username_3**: Btw, this is not a blog.  

---

## 1 answers

### Answer by username_1 on 2010-12-21. Score: 5

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.

> **Comments:**
> **username_2**: 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.)  
> **username_1**: 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.  

---

