Suppose I have a probabilistic Turing machine for a language such that $$ x \in A \implies \Pr(M \text{ accepts } x) \ge \frac{1}{n}$$ $$ x \notin A \implies \Pr(M \text{ accepts } x) = 0$$
I want to show that the above language is in $\mathsf{RP}$. In particular, I need a probabilistic Turing machine $N$ such that $$ x \in A \implies \Pr(N \text{ accepts } x) \ge 1 - \frac{1}{2^n}$$ where $n = |x|$.

I tried to construct $N$ such that it runs $M$ multiple times (say $t$ times) and accepts if at least one of the runs accepts. This preserves the one-sided error but I'm not sure if it runs in polynomial time.

I showed that $x \in A \implies \Pr(N \text{ accepts } x) \ge 1 - (1 - \frac{1}{n})^t$.

Now, to show that it is in $\mathsf{RP}$,

$$1 - (1 - \frac{1}{n})^t \ge 1 - \frac{1}{2^n}$$ $$ (1-\frac{1}{n})^t \le \frac{1}{2^n} $$

I am basically stuck at this point and unable to show an upper bound for $t$. I know that it suffices to show that $t$ is polynomial in $n$ but I am not able to prove it. How do I show that $N$ is indeed a polynomial time machine? Or maybe this is not the right approach?

  • $\begingroup$ Solve for t. ​ ​ $\endgroup$ – user12859 Feb 11 '17 at 16:09
  • $\begingroup$ @RickyDemer I tried doing that by taking log on both sides, but that is giving me a lower bound for t. $\endgroup$ – skankhunt42 Feb 11 '17 at 16:11
  • $\begingroup$ You don't need an upper bound on what t suffice, you just need an upper bound on what t are necessary. ​ ​ $\endgroup$ – user12859 Feb 11 '17 at 16:15
  • $\begingroup$ @RickyDemer Could you please expand on that? I don't understand. $\endgroup$ – skankhunt42 Feb 11 '17 at 16:19
  • 1
    $\begingroup$ You could also use a quadratic with a sufficiently-large coefficient. ​ ​ $\endgroup$ – user12859 Feb 11 '17 at 16:27

Your Answer

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

Browse other questions tagged or ask your own question.