Given a $\#P$ function $f(x)$, we can use Stockmeyer's counting theorem to get an approximation $g(x)$ such that \begin{equation} \left(1 - \frac{1}{\text{poly}(n)} \right) f(x) \le g(x) \le \left(1 + \frac{1}{\text{poly}(n)} \right) f(x), \end{equation} using a $\text{BPP}^{\text{NP}}$ algorithm. How much better of an approximation can we get if we go higher up in the polynomial hierarchy? Is there a no-go result saying this is very close to the best approximation that we can hope for?

  • $\begingroup$ Background: rjlipton.wordpress.com/2009/08/27/… $\endgroup$ Mar 2, 2021 at 11:18
  • $\begingroup$ I did look into this, but it doesn't say whether there is a better approximation if we go higher up in the hierarchy. $\endgroup$
    – AngryLion
    Mar 2, 2021 at 18:32
  • $\begingroup$ I'm sorry for the previous comment being so short. The comment was meant as an aid to readers of the question (like me) who need to google first what Stockmeyer's counting Theorem is, in what paper it was originally proved and something like that. $\endgroup$ Mar 2, 2021 at 18:53


Your Answer

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

Browse other questions tagged or ask your own question.