<p>This is #P-hard, already for an arbitrary fixed constant approximation factor. As you noted, it allows you to approximate <span class="math-container">$|f(x)|$</span> for any GapP-function <span class="math-container">$f$</span>, and therefore if <span class="math-container">$f$</span> is any #P (or GapP) function, it allows you to approximate <span class="math-container">$|f(x)-y|$</span> for a given <span class="math-container">$y$</span>. With this, you can still compute <span class="math-container">$f(x)$</span> by a form of binary search.</p>
<p>Specifically, fix a constant <span class="math-container">$k\ge\gamma^2+1$</span>, where <span class="math-container">$\gamma&gt;1$</span> is the approximation factor. Starting with an initial estimate <span class="math-container">$0\le f(x)\le 2^{n^c}$</span>, if you already have <span class="math-container">$a_0&lt;a_1$</span> such that <span class="math-container">$a_0\le f(x)\le a_1$</span>, you compute <span class="math-container">$a'_0\le a'_1$</span> such that <span class="math-container">$a'_0\le f(x)\le a'_1$</span> and <span class="math-container">$a'_1-a'_0\le\lfloor(1-\frac1k)(a'_1-a'_0)\rfloor$</span> by computing the approximations <span class="math-container">$d_0,d_1$</span> such that
<span class="math-container">$$\gamma^{-1}d_i\le|f(x)-a_i|\le\gamma d_i,$$</span>
and putting
<span class="math-container">$$[a'_0,a'_1]=\begin{cases}\bigl[a_0,a_1-\lceil\frac1k(a_1-a_0)\rceil\bigr]&amp;d_0\le d_1,\\{}\bigl[a_0+\lceil\frac1k(a_1-a_0)\rceil,a_1\bigr]&amp;\text{otherwise.}\end{cases}$$</span>
To see that this is correct: if, for example, <span class="math-container">$d_0\le d_1$</span>, then
<span class="math-container">$$f(x)-a_0\le\gamma^2(a_1-f(x)),$$</span>
hence
<span class="math-container">$$f(x)\le\frac{a_0+\gamma^2a_1}{\gamma^2+1}=a_1-\frac{a_1-a_0}{\gamma^2+1}\le a_1-\frac{a_1-a_0}k.$$</span>
The case <span class="math-container">$d_1\ge d_0$</span> is symmetric.</p>

CC BY-SA 4.0
2021-04-29T07:28:06.330Z
2021-04-29T07:28:06.330Z
Emil Jeřábek
<p>Consider the functions included in the complexity class GapP.</p>
<p>We know that approximating a function from GapP, in the worst case, to inverse polynomial multiplicative error, is #P-hard. Even correctly finding the sign of <span class="math-container">$f(x)$</span> (for a worst case function <span class="math-container">$f$</span>) is #P-hard --- if we can find the sign, we can use a padding argument, coupled with binary search, to exactly find the value of the function. (For reference, see <a href="https://www.youtube.com/watch?v=8zn8YJ5hUH8&amp;t=2240s" rel="nofollow noreferrer">this</a>.)</p>
<p>Now, consider another class of functions: let's name the class SpecialGap. A function <span class="math-container">$g(x)$</span> belongs to SpecialGap if and only if there exists a GapP function <span class="math-container">$f(x)$</span> such that <span class="math-container">$g(x) = f(x)^{2}$</span>.</p>
<p>Note some properties of SpecialGap. In the worst case, computing the sign of a function in SpecialGap is easy --- it is always positive, as it is the square of a function. In the worst case, exactly computing a function from SpecialGap is #P-hard --- noting that #P functions are a subset of GapP functions, if we want to exactly estimate the value of a #P function, we use the procedure we have for finding the exact value of a SpecialGap function to find the exact value of the square of our desired #P function, and then we just take the square root to get the exact value of our #P function. Note that exactly estimating the value of a #P function is #P-hard.</p>
<p>Is multiplicatively estimating the value of a worst-case function, to inverse polynomial error, from SpecialGap also #P-hard?</p>
<hr />
<p>Here's an attempt at a proof.</p>
<p>Consider a procedure to multiplicatively estimate (upto inverse polynomial relative error) the value of a SpecialGap function <span class="math-container">$g(x)$</span>, where <span class="math-container">$g(x) = f(x)^{2}$</span>, for a GapP function <span class="math-container">$f(x)$</span>. Let the estimate be <span class="math-container">$\tilde g(x)$</span>, where</p>
<p><span class="math-container">\begin{equation}
\left(1 - \frac{1}{p}\right)f(x)^{2} \leq \tilde g(x) \leq \left(1 + \frac{1}{p}\right)f(x)^{2},
\end{equation}</span>
for some polynomially bounded function <span class="math-container">$p$</span>. Taking the square root, we have</p>
<p><span class="math-container">\begin{equation}
\left(1 - \frac{1}{2p}\right)|f(x)| \leq \sqrt{\tilde g(x)} \leq \left(1 + \frac{1}{2p}\right)|f(x)|,
\end{equation}</span>
which is an inverse polynomial multiplicative error estimate to <span class="math-container">$|f(x)|$</span>.</p>
<p>The proof now reduces to proving that for a function <span class="math-container">$f(x)$</span> belonging to GapP, in the worst case, it is #P-hard to have an inverse polynomial multiplicative error estimate to <span class="math-container">$|f(x)|$</span>. I didn't have any idea on how to prove this. For one, since <span class="math-container">$|f(x)|$</span> is always positive, making use of a procedure to find the sign of <span class="math-container">$|f(x)|$</span>, and then using binary search and padding, fails.</p>

<cc.complexity-theory><complexity-classes><counting-complexity><complexity>
Relative error estimation of a special type of GapP function
AngryLion
# Relative error estimation of a special type of GapP function

(Asked by: username_0 on 2021-04-29)

Consider the functions included in the complexity class GapP.

We know that approximating a function from GapP, in the worst case, to inverse polynomial multiplicative error, is #P-hard. Even correctly finding the sign of $f(x)$ (for a worst case function $f$) is #P-hard --- if we can find the sign, we can use a padding argument, coupled with binary search, to exactly find the value of the function. (For reference, see [this](https://www.youtube.com/watch?v=8zn8YJ5hUH8&t=2240s).)

Now, consider another class of functions: let's name the class SpecialGap. A function $g(x)$ belongs to SpecialGap if and only if there exists a GapP function $f(x)$ such that $g(x) = f(x)^{2}$.

Note some properties of SpecialGap. In the worst case, computing the sign of a function in SpecialGap is easy --- it is always positive, as it is the square of a function. In the worst case, exactly computing a function from SpecialGap is #P-hard --- noting that #P functions are a subset of GapP functions, if we want to exactly estimate the value of a #P function, we use the procedure we have for finding the exact value of a SpecialGap function to find the exact value of the square of our desired #P function, and then we just take the square root to get the exact value of our #P function. Note that exactly estimating the value of a #P function is #P-hard.

Is multiplicatively estimating the value of a worst-case function, to inverse polynomial error, from SpecialGap also #P-hard?

---

Here's an attempt at a proof.

Consider a procedure to multiplicatively estimate (upto inverse polynomial relative error) the value of a SpecialGap function $g(x)$, where $g(x) = f(x)^{2}$, for a GapP function $f(x)$. Let the estimate be $\tilde g(x)$, where

\begin{equation}
\left(1 - \frac{1}{p}\right)f(x)^{2} \leq \tilde g(x) \leq \left(1 + \frac{1}{p}\right)f(x)^{2},
\end{equation}
for some polynomially bounded function $p$. Taking the square root, we have

\begin{equation}
\left(1 - \frac{1}{2p}\right)|f(x)| \leq \sqrt{\tilde g(x)} \leq \left(1 + \frac{1}{2p}\right)|f(x)|,
\end{equation}
which is an inverse polynomial multiplicative error estimate to $|f(x)|$.

The proof now reduces to proving that for a function $f(x)$ belonging to GapP, in the worst case, it is #P-hard to have an inverse polynomial multiplicative error estimate to $|f(x)|$. I didn't have any idea on how to prove this. For one, since $|f(x)|$ is always positive, making use of a procedure to find the sign of $|f(x)|$, and then using binary search and padding, fails.

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


---

## 1 answers

### Answer by username_1 on 2021-04-29. Score: 1 | Accepted answer

This is #P-hard, already for an arbitrary fixed constant approximation factor. As you noted, it allows you to approximate $|f(x)|$ for any GapP-function $f$, and therefore if $f$ is any #P (or GapP) function, it allows you to approximate $|f(x)-y|$ for a given $y$. With this, you can still compute $f(x)$ by a form of binary search.

Specifically, fix a constant $k\ge\gamma^2+1$, where $\gamma>1$ is the approximation factor. Starting with an initial estimate $0\le f(x)\le 2^{n^c}$, if you already have $a\_0 such that $a\_0\le f(x)\le a\_1$, you compute $a'\_0\le a'\_1$ such that $a'\_0\le f(x)\le a'\_1$ and $a'\_1-a'\_0\le\lfloor(1-\frac1k)(a'\_1-a'\_0)\rfloor$ by computing the approximations $d\_0,d\_1$ such that
$$\gamma^{-1}d\_i\le|f(x)-a\_i|\le\gamma d\_i,$$
and putting
$$[a'\_0,a'\_1]=\begin{cases}\bigl[a\_0,a\_1-\lceil\frac1k(a\_1-a\_0)\rceil\bigr]&d\_0\le d\_1,\\{}\bigl[a\_0+\lceil\frac1k(a\_1-a\_0)\rceil,a\_1\bigr]&\text{otherwise.}\end{cases}$$
To see that this is correct: if, for example, $d\_0\le d\_1$, then
$$f(x)-a\_0\le\gamma^2(a\_1-f(x)),$$
hence
$$f(x)\le\frac{a\_0+\gamma^2a\_1}{\gamma^2+1}=a\_1-\frac{a\_1-a\_0}{\gamma^2+1}\le a\_1-\frac{a\_1-a\_0}k.$$
The case $d\_1\ge d\_0$ is symmetric.


---

