<p>Given a <span class="math-container">$\#P$</span> function <span class="math-container">$f(x)$</span>, we can use Stockmeyer's counting theorem to get an approximation <span class="math-container">$g(x)$</span> such that
<span class="math-container">\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}</span>
using a <span class="math-container">$\text{BPP}^{\text{NP}}$</span> 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?</p>

CC BY-SA 4.0
2021-03-02T11:18:11.070Z
Background: https://rjlipton.wordpress.com/2009/08/27/stockmeyers-approximate-counting-method/
Hermann Gruber
CC BY-SA 4.0
2021-03-02T18:32:16.780Z
I did look into this, but it doesn't say whether there is a better approximation if we go higher up in the hierarchy.
AngryLion
CC BY-SA 4.0
2021-03-02T18:53:08.383Z
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.
Hermann Gruber
<cc.complexity-theory><complexity-classes><approximation-algorithms><counting-complexity><approximation-hardness>
Improving the approximation in Stockmeyer's counting theorem
AngryLion
# Improving the approximation in Stockmeyer's counting theorem

(Asked by: username_0 on 2021-03-01)

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?

**Tags:** cc.complexity-theory, complexity-classes, approximation-algorithms, counting-complexity, approximation-hardness

> **Comments:**
> **username_1**: Background: https://rjlipton.wordpress.com/2009/08/27/stockmeyers-approximate-counting-method/  
> **username_0**: I did look into this, but it doesn't say whether there is a better approximation if we go higher up in the hierarchy.  
> **username_1**: 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.  

---

## 0 answers

