0
$\begingroup$

Let $0 \le \alpha \le 1$. The complexity classs $\mathsf{RP}_\alpha$ consists of all languages $L$ for which we can find a probabilistic polynomial time Turing machine which satisfies the following conditions:

  • $w \in L \Rightarrow \Pr[\text{accept}] \geq \alpha$.
  • $w \notin L \Rightarrow \Pr[\text{accept}] = 0$.

We define $\mathsf{RP}$ to be $\mathsf{RP}_{1/2}$.

  1. How would I show that if $0 < \alpha < 1$ then $\mathsf{RP}_\alpha = \mathsf{RP}$ using reliability amplification?
  2. How would I show that when $\alpha = 1$, $\mathsf{RP}_\alpha = \mathsf{P}$?
$\endgroup$
2
  • $\begingroup$ This is a very standard exercise. You can see it worked out in lecture notes and textbooks. $\endgroup$ Apr 29 '21 at 6:43
  • $\begingroup$ I believe you can solve question 2 on your own. $\endgroup$ Apr 29 '21 at 6:44