World's most popular travel blog for travel bloggers.

# Approximating the set of witnesses of a BPP algorithm

, ,
Problem Detail:

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.

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.