If $NP=RP$ then $NP$ is easy on average. Then from point $1$ in abstract in http://lance.fortnow.com/papers/files/derand.pdf which says $NP$ is easy on average implies $P=BPP$ do we have $NP=RP\implies P=NP$?

This problem asks directly a point with respect to a remark in a paper.

I do not blindly ask if np=rp then is p=np. I ask about a comment in a paper.

I think essentially I am asking is $RP\subseteq Avg-P$?


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.