<p>Consider a GapP function <span class="math-container">$g(x)$</span> for <span class="math-container">$x \in \{0, 1\}^{*}$</span>. Consider an approximation <span class="math-container">$\tilde g(x)$</span> such that</p>
<p><span class="math-container">\begin{equation}
\left|g(x) - \tilde g(x)\right| \leq \epsilon.
\end{equation}</span></p>
<p>Consider a few cases.</p>
<p>Case 1: <span class="math-container">$\epsilon = 2^{n-1}$</span>.</p>
<p>Case 2: <span class="math-container">$\epsilon = 2^{n-1} - \text{poly}(n)$</span>.</p>
<p>Case 3: <span class="math-container">$\epsilon = 2^{n}/\text{poly}(n)$</span>.</p>
<p>Case 4:  <span class="math-container">$\epsilon = 2^{cn - o(n)}$</span>, <span class="math-container">$c &lt; 1$</span>.</p>
<p>From <a href="https://cstheory.stackexchange.com/questions/22387/approximating-p-hard-problems">this</a> answer, we know that if <span class="math-container">$g(x)$</span> is a #P function, then the first three cases are easy (have a BPP algorithm), and the fourth case is #P-hard.</p>
<p>Are all these cases #P-hard when <span class="math-container">$g(x)$</span> is a GapP function? If so, is there any value of <span class="math-container">$\epsilon$</span> for which approximating a GapP function is &quot;easy&quot; (doable in BPP/the polynomial hierarchy)?</p>

CC BY-SA 4.0
2021-03-17T11:33:06.527Z
While not directly answering you question, this paper discusses related questions about the hardness of additive approximations of GapP functions. https://arxiv.org/pdf/0908.2122.pdf
Martin Schwarz
CC BY-SA 4.0
2021-03-17T12:04:45.740Z
Any GapP function is the difference of two #P functions, thus you can approximate it with additive error $2^n/\mathrm{poly}(n)$ (i.e., cases 1–3) in randomized polynomial time by just approximating the two #P functions. (This is not BPP, by the way. BPP is a class of languages. The class of functions that can be approximated in randomized polynomial time is, up to scaling, the somewhat obscure class APP of Kabanets, Rackoff, and Cook. Up to polynomial-time Turing reductions, this is equivalent to promise-BPP, which is more general than BPP.)
Emil Jeřábek
CC BY-SA 4.0
2021-04-16T09:48:00.843Z
Given just an efficient description of a GapP function $g(x)$, how do we approximate the two #P functions? Do we somehow require those two #P functions to be provided to us as oracles?
AngryLion
CC BY-SA 4.0
2021-04-16T09:50:34.007Z
As in, I presume way this estimation/approximation procedure works usually is by Monte Carlo methods. But, if we are given a description of a GapP function $g(x)$, we can only apply the Monte Carlo method on $g(x)$ --- not its individual #P components. Isn't that a problem?
AngryLion
<cc.complexity-theory><complexity-classes><time-complexity><counting-complexity>
Additive error approximations of GapP functions
AngryLion
# Additive error approximations of GapP functions

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

Consider a GapP function $g(x)$ for $x \in \{0, 1\}^{\*}$. Consider an approximation $\tilde g(x)$ such that

\begin{equation}
\left|g(x) - \tilde g(x)\right| \leq \epsilon.
\end{equation}

Consider a few cases.

Case 1: $\epsilon = 2^{n-1}$.

Case 2: $\epsilon = 2^{n-1} - \text{poly}(n)$.

Case 3: $\epsilon = 2^{n}/\text{poly}(n)$.

Case 4: $\epsilon = 2^{cn - o(n)}$, $c < 1$.

From [this](https://cstheory.stackexchange.com/questions/22387/approximating-p-hard-problems) answer, we know that if $g(x)$ is a #P function, then the first three cases are easy (have a BPP algorithm), and the fourth case is #P-hard.

Are all these cases #P-hard when $g(x)$ is a GapP function? If so, is there any value of $\epsilon$ for which approximating a GapP function is "easy" (doable in BPP/the polynomial hierarchy)?

**Tags:** cc.complexity-theory, complexity-classes, time-complexity, counting-complexity

> **Comments:**
> **username_1**: While not directly answering you question, this paper discusses related questions about the hardness of additive approximations of GapP functions. https://arxiv.org/pdf/0908.2122.pdf  
> **username_2**: Any GapP function is the difference of two #P functions, thus you can approximate it with additive error $2^n/\mathrm{poly}(n)$ (i.e., cases 1–3) in randomized polynomial time by just approximating the two #P functions. (This is not BPP, by the way. BPP is a class of languages. The class of functions that can be approximated in randomized polynomial time is, up to scaling, the somewhat obscure class APP of Kabanets, Rackoff, and Cook. Up to polynomial-time Turing reductions, this is equivalent to promise-BPP, which is more general than BPP.)  
> **username_0**: Given just an efficient description of a GapP function $g(x)$, how do we approximate the two #P functions? Do we somehow require those two #P functions to be provided to us as oracles?  
> **username_0**: As in, I presume way this estimation/approximation procedure works usually is by Monte Carlo methods. But, if we are given a description of a GapP function $g(x)$, we can only apply the Monte Carlo method on $g(x)$ --- not its individual #P components. Isn't that a problem?  

---

## 0 answers

