World's most popular travel blog for travel bloggers.

Approximating the set of witnesses of a BPP algorithm

, , No Comments
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.

Asked By : iHubble
Answered By : D.W.

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.

Best Answer from StackOverflow

Question Source :

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback