# construct language in ${\sf BPP \backslash (RP \cup coRP)}$ assuming $\sf RP \neq ZPP$

### Problem

This is a HW problem from CMU 15-455 (hw10, p1(a)), spring 17 by Ryan O'Donnell.

Assume $$L \in {\sf RP \backslash ZPP}$$. Define $$L' = \left\{ (x, y) : \text{either x \in L and y \notin L, or vice versa} \right\},$$ Prove that $$L' \notin {\sf RP} \cap {\sf coRP}$$.

### My Thoughts

The path of this proof is clear: show that $$L' \in {\sf RP}$$ (or $${\sf coRP}$$) implies $$L \in {\sf coRP}$$, thus $$L \in {\sf ZPP}$$, contradicts the assumption. Here I consider to prove $$L' \in {\sf RP} \implies L \in {\sf coRP}$$ first, but the following points give a conclusion that stuck me:

1. I don't know any property/information about the language $$L$$ itself, only a checker $$A$$ is given.
2. To exploit checker $$B$$ of $$L'$$, two different strings are needed. Pairs of identical strings like $$(x, x)$$ are not in $$L'$$ thus will always be rejected, gives no information b/c rejection by $$B$$ can stand for both valid and invalid, although error probability can be arbitrarily small (but never be 0).
3. If I want to ensure $$x \notin L$$ with no error, I must choose a string $$y \in L$$ since only acceptance by $$B$$ is "absolutely correct". But how can I find such $$y$$ in such a way that can work for every possible $$L$$ and for every time it runs?
4. If I look for a random string $$y$$ from the street, the probability of success depends on $$|L \cap \Sigma^n|$$, but it's unknown.

Here the only way I can imagine is to "pre-calculate" such string $$y \in L$$, then $$L' \in {\sf RP} \implies L \in {\sf coRP}$$ follows directly. But how can I sure that such $$y$$ can always be found, within an acceptable time complexity? I'm not sure about this point, so I asked the question How to decide complexity affected by 'magic number'? It seems that this is an acceptable solution, but I'm not sure still. So I ask this question here, and I hope you you can point out some elegant solutions that I haven't found. Thanks!

To show $$L'\notin \mathsf{RP \cup coRP}$$ you can essentially follow the proof of $$\mathsf{ZPP=RP\cap coRP}$$.
Since $$L\neq \Sigma^*,\varnothing$$ (otherwise it's in ZPP), there exist $$y_1\in L, y_2\notin L$$. Note that you don't have to find $$y_1,y_2$$ at runtime, as you can simply hardcode them into your machine for $$L'$$. If $$L'\in RP$$, then you can simultaneously run $$M_L(x)$$ and $$M_{L'}(x,y_1)$$ where $$M_L,M_{L'}$$ are the RP machines for $$L,L'$$ correspondingly. If $$L'\in coRP$$ then you can simultaneously run $$M_L(x), M_{\overline{L'}}\left(x,y_2\right)$$.
• I don't see a concrete suggestion for a ZPP machine for $L$ in your post, but if the only thing that was bothering you was how to find a fixed string outside/inside the language, then yes - this is addressed by hardcoding them into the machine. Jul 29 at 7:19