The Relationship between P^NP and the Permanent

Question

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.

Answer 1

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.