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 1


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<a_1$ 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.