It is not really clear to me, how and if I can do boosting for correctness (or error reduction) on a BPP (bounded-error probabilistic polynomial-time) search problem. Can anyone of you explain me how it works?

With BPP search, I mean a problem that can have false positive-negative, correct solution, and no-solution. Here's a definition:

A probabilistic polynomial-time algorithm $A$ solves the search problem of the relation $R$ if

  • for every $x ∈ S$, $Pr[A(x) ∈ R(x)] > 1 - μ(|x|)$
  • for every $x ∉ SR$, $Pr[A(x) = \text{no-solution}] > 1 - μ(|x|)$

were $R(x)$ is the set of solution for the problem and $μ(|x|)$ is a negligible function (it is rare that it fails).

So now I would like to increase my probability of getting a good answer, how can I do it?

~ ".. boosting for correctness.." : a way to increase the probability of the algorithm (generally by multile runs of the probabilistic algorithm), i.e., when the problem have a solution then the algorithm likely return a valid one.

  • 1
    $\begingroup$ Make clear what BPP stands for (at least add a link), also explain what "boosting for correctness" means. $\endgroup$
    – A.Schulz
    Nov 6 '12 at 8:37
  • 1
    $\begingroup$ you got the definition wrong. For (standard) BPP, $\mu(x)=1/3$. Then to get a negligible $\mu$ one just performs repetitions of the algorithm and takes the majority of the answers. Due to Chernoff bound, the probability that the majority of the results are incorrect is negligibly small. $\endgroup$
    – Ran G.
    Nov 7 '12 at 6:27
  • 1
    $\begingroup$ I think you actually make a very good point here: I think the boosting only works if your problem lies in $\mathbf{NP}$ (or $\mathbf{coNP}$ for the other error bound). This might be a widespread belief because most problems for which we develop $\mathbf{BPP}$ algorithms are also in $\mathbf{NP}$. As the relation between $\mathbf{NP}$ and $\mathbf{BPP}$ is not known, I guess that it is also not known whether this always works. $\endgroup$ Nov 7 '12 at 22:21

If the relation $R$ lies in the complexity class P (or even BPP), then boosting works by running your algorithm many times, and testing whether its output satisfies $R$. When $x \in S$, this fails with probability $\mu^N$, where $N$ is the number of times you run $A$. When $x \notin S$, this never fails. This way you can boost $\mu$ from $1-1/\mathrm{poly}(n)$ to $2^{-\mathrm{poly}(n)}$.

Edit: if $R$ is in BPP rather than P, with constant error probability $\mu$, then this approach doesn't work. You can decide whether $x \in S$ or not using the usual majority trick, but if $x \in S$, it's not clear how you'd find a correct witness whp.

  • $\begingroup$ thank you for the answer, but is not really clear why μ(x)=1/3, should not it decrease faster, on the relevand parameter x? $\endgroup$
    – LMG
    Nov 7 '12 at 13:54
  • $\begingroup$ $\mu(x) = 1/3$ by definition. If $R \in P$ then $\mu$ can be boosted to $3^{-n^k}$ for any $k$ by just running the algorithm $n^k$ times. $\endgroup$ Nov 7 '12 at 14:20
  • $\begingroup$ but how can you say that "When x∉S, this never fails"? this R is in BPP not in RP.. Thanks for reply $\endgroup$
    – LMG
    Nov 7 '12 at 14:58
  • $\begingroup$ You're right, I was assuming that $R$ is in P. $\endgroup$ Nov 8 '12 at 6:49

Your Answer

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

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