I believe its true but struggle to prove. I know NP=union over positive c's of RP(2^-(n^c)) and from here to prove that RP(1/2^n) contained in NP is immediate. the other side is the problem.

I've tried the following: Given L in NP and a polynomial verifier V for L with polynomial P, to use a random Turing machine M. M, given a word w, uses its random input to guess a witness c in the range of P(n)(upper bound to the witness length because otherwise we would get a higher runtime than P(n) just to read the witness), and run V(w,c) and answer accordingly. its run time is polynomial.

Now let's construct a TM - M' which given a word (of length n) runs M with the word w, F(n) times (when F is a polynomial we can choose). If in one of the runs M returned 1 - return 1 (w is in L). Otherwise return 0. M' RUNTIME is polynomial, but I'm stuck at proving that - for every polynomial P, there exist a polynomial F such that there exists N , s.t for every n>N, for every word w in L, P[M'(w)=1] >= 2^-n. (which means L is in RP(2^-n))

The inequality I got is the following:


On the LHS there's the complement to 1 of probability that M will not guess the right witness to the verifier in each run (the probability M will choose the right witness length - 1/P(n) mull the probability M will choose the right witness out of all the witnesses in length p(n) (worst-case)), multiplied by itself f(n) times as this is the number of times M' runs M.

It's exactly the probability that M' will determine w is in L (if it's in L).

I would appreciate your help understanding whether the claim is true, and if so how to prove/finish my proof.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.