[Solved]: BPP search: what does boosting correctness entail?

Problem Detail: 

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.

Asked By : LMG

Answered By : Yuval Filmus

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/6503

3.2K people like this

 Download Related Notes/Documents