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

  • $\begingroup$ While not directly answering you question, this paper discusses related questions about the hardness of additive approximations of GapP functions. arxiv.org/pdf/0908.2122.pdf $\endgroup$ – Martin Schwarz Mar 17 at 11:33
  • 1
    $\begingroup$ 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.) $\endgroup$ – Emil Jeřábek Mar 17 at 12:04
  • $\begingroup$ 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? $\endgroup$ – AngryLion Apr 16 at 9:48
  • $\begingroup$ 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? $\endgroup$ – AngryLion Apr 16 at 9:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.