# BPP search: what does boosting correctness entail?

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.

-
Make clear what BPP stands for (at least add a link), also explain what "boosting for correctness" means. –  A.Schulz Nov 6 '12 at 8:37
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. –  Ran G. Nov 7 '12 at 6:27
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. –  Alex ten Brink 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.
$\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. –  Yuval Filmus Nov 7 '12 at 14:20
You're right, I was assuming that $R$ is in P. –  Yuval Filmus Nov 8 '12 at 6:49