1
$\begingroup$

The definition of ZPP seems to be

$$ZPP = RP \cap coRP.$$

I think ZPP should then be equivalent to P, because for any language L in ZPP, there is an algorithm A and B proving that it is in RP and coRP, respectively. Since A must tell for any x s.t. $x \notin L$ the truth and B for any x s.t. $x \notin L$ as well, we can just run both algorithms in polynomial time, and one of them has to give me the answer since these are the only two possible options.

Is there an error in my thoughts?

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
5
$\begingroup$

There is an error in your reasoning. Say that $x \not\in L$. Then when you run $A(x)$ you'll get a "no" answer with certainty. However, when you run $B(x)$ you'll get a "no" with some probability that can be up to $1/2$.

What do you do when both $A(x)$ and $B(x)$ return "no"? In order to answer correctly you'd need to return "no".

Consider now $x \in L$. $A(x)$ will return "no" with some probability that can be up to $1/2$, while $B(x)$ will return "no" with certainty. We already argued that you algorithm returns "no" in this case, but this is incorrect.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Nice explanation, but is also worth mentioning that the particular error in the reasoning is that "and one of them has to give me the answer since these are the only two possible options." is simply wrong; both give answers, and you know that one of them must be correct but you don't know which one. This is trivial as you can replace them by $\Sigma^\star$ and $\varnothing$. $\endgroup$
    – Bernardo Subercaseaux
    Commented Jun 18, 2023 at 20:13
  • 1
    $\begingroup$ Yeah. There are $3$ possible combinations of the two answers. If $x \in L$ you get one of $\{(yes, no), (no, no)\}$. If $x \not\in L$ you get one of $\{ (no, yes), (no, no) \}$. If you you need to decide $x \in L$ and you observe the output of $A$ and $B$ then you can answer correctly when you see either $(yes, no)$ or $(no, yes)$. However, the answers $(no, no)$ are inconclusive (or, if you wish, you don't know which of the two algorithms was incorrect). $\endgroup$
    – Steven
    Commented Jun 18, 2023 at 20:25

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.