Let $\mathcal{A}$ be a randomized algorithm that decides a language $\mathcal{L}$. For each input $x\in\mathcal{L}$, we define the set of witnesses of $x$ as $W(\mathcal{A},x) = \{r\in\{0,1\}^n:\mathcal{A}(x,r) \text{ accepts}\}$. Suppose that $\mathcal{A}$ is a $\mathsf{BPP}$ algorithm. We wish to show that there exists an algorithm $\mathcal{A}'$ also deciding $\mathcal{L}$ such that $$ |W(\mathcal{A}',x)| \geq \frac{2^n}{4}, \qquad \text{and} \qquad \big|\{0,1\}^n - W(\mathcal{A}', x)\big| \geq \frac{2^n}{4} $$ for all input $x\in\mathcal{L}$.

I am sincerely lost for this problem. An idea that was vaguely suggested to me was to flip two fair coins and proceed based on the result: trivially accept if the result is $(1,1)$, trivially reject if it's $(0,0)$ and run the $\mathsf{BPP}$ algorithm for the other two remaining cases. However, I am not sure how exactly that could be of any help, of if another way can be found.

Any help would be appreciated.


1 Answer 1


The idea suggested to you was helpful. It basically amounts to suggesting a candidate algorithm $\mathcal{A}'$.

Your next step is to try bounding $|W(\mathcal{A}',x)|$ and $|\{0,1\}^n - W(\mathcal{A}',x)|$ for that choice of $\mathcal{A}'$. See what you can come up with. See if you can relate $|W(\mathcal{A}',x)|$ to $|W(\mathcal{A},x)|$ etc.

  • $\begingroup$ Could you explicit a little bit more on bounding the given quantities? I very much appreciate your comment, but it is more a rewording of my concerns rather than an answer. For instance, why is this algorithm still in $\mathsf{BPP}$? $\endgroup$
    – iHubble
    Apr 22, 2015 at 20:45
  • $\begingroup$ @iHubble, this is your exercise, so you should take the next step. I'm suggesting a next step you could take -- I would suggest editing your question to show the tightest bounds on those two quantities you were able to come up with. As far as why $\mathcal{A}'$ is in BPP: try plugging into the definition. What are the requirements for an algorithm to be in BPP? Does $\mathcal{A}'$ satisfy them? What part can you prove, and what part are you stuck on? Even if you're not sure about one or two of the requirements, you should be able to give at least a partial answer. $\endgroup$
    – D.W.
    Apr 22, 2015 at 20:50
  • $\begingroup$ @DW Fair enough, I'm really tired and just realized how silly that sounds. The $\mathsf{RP}$ case looks a little bit more tricky, I'll get a nice rest and give it a shot. $\endgroup$
    – iHubble
    Apr 22, 2015 at 20:52
  • $\begingroup$ No problem, @iHubble, hope you're feeling more rested soon! $\endgroup$
    – D.W.
    Apr 22, 2015 at 20:53
  • $\begingroup$ Hello, I'm sorry for digging up an older topic but I stumbled upon this question and it seems interesting. To my mind $\cal A'$ is not a $\mathbf{BPP}$ algorithm as the probability of making a mistake is equal to $1/4 + 1/2\mathbb{P}(\cal A\textrm{ makes a mistake}) = 5/12>1/3$ (if we assume a $\mathbf{BPP}$ algorithm needs to have its error bounded by $1/3$. $\endgroup$
    – Jules
    Apr 14, 2018 at 15:32

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.