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 Gruber Mar 2 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 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 Gruber Mar 2 at 18:53
Add a comment
|
