# Relative error estimation of a special type of GapP function

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.)

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.

## 1 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.