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$
$\endgroup$
3
-
$\begingroup$ Background: rjlipton.wordpress.com/2009/08/27/… $\endgroup$– Hermann GruberMar 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$– AngryLionMar 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$– Hermann GruberMar 2, 2021 at 18:53
Add a comment
|