I am looking for a reference to the fact that if NP is included in BPP then NP is equal to RP. See for instance these links:

I know that this is folklore, but I'd still like to cite something that is published and where this would be properly proved.

  • 5
    $\begingroup$ At this point in history, I don't know if this needs a citation, e.g. it is regularly given as an exercise. (I also don't know if there is such a citation, or if it was always just an exercise.) $\endgroup$ Dec 21, 2019 at 16:49

1 Answer 1


An actual factual reference is

K. Ko. Some observations on the probabilistic algorithms and NP-hard problems. Information Processing Letters, 14(1):39–43, 1982.

(When I first saw this result --- I don't remember where it was now --- it was called "Ko's Theorem". Googling suggests that another theorem has that name as well...)

  • 1
    $\begingroup$ Nice - I didn't know it actually existed in the literature! $\endgroup$ Dec 23, 2019 at 4:57

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.