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
    Commented Nov 6, 2012 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.
    Commented Nov 7, 2012 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$ Commented Nov 7, 2012 at 22:21

1 Answer 1


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
    Commented Nov 7, 2012 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$ Commented Nov 7, 2012 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
    Commented Nov 7, 2012 at 14:58
  • $\begingroup$ You're right, I was assuming that $R$ is in P. $\endgroup$ Commented Nov 8, 2012 at 6:49

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.