1
$\begingroup$

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

Improve this question
$\endgroup$
4
  • $\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
    Commented Mar 17, 2021 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
    Commented Mar 17, 2021 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
    Commented Apr 16, 2021 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
    Commented Apr 16, 2021 at 9:50

0

Reset to default

Your Answer

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