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!


1 Answer 1


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)$.

  • $\begingroup$ It seems that the part of your answer that goes further than what I described is "hardcode", do I understand it correctly? $\endgroup$
    – Marcythm
    Jul 29 at 7:08
  • $\begingroup$ 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. $\endgroup$
    – Ariel
    Jul 29 at 7:19
  • $\begingroup$ got it, thanks. (I didn't describe how to construct ZPP from RP + coRP b/c I thought this is obvious, but also thanks for pointing this out.) $\endgroup$
    – Marcythm
    Jul 29 at 9:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.