<p>An actual factual reference is </p>

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

<p>(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...) </p>

CC BY-SA 4.0
2019-12-23T04:57:15.883Z
Nice - I didn't know it actually existed in the literature!
Joshua Grochow
CC BY-SA 4.0
2019-12-22T20:40:23.730Z
2019-12-22T20:40:23.730Z
Ryan Williams
<p>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:</p>

<ul>
<li><a href="https://cs.stackexchange.com/q/80509">https://cs.stackexchange.com/q/80509</a></li>
<li><a href="http://www.inf.ed.ac.uk/teaching/courses/cmc/cw3_solns.pdf" rel="noreferrer">http://www.inf.ed.ac.uk/teaching/courses/cmc/cw3_solns.pdf</a></li>
<li><a href="https://www.csie.ntu.edu.tw/~lyuu/complexity/2011/20120103s.pdf" rel="noreferrer">https://www.csie.ntu.edu.tw/~lyuu/complexity/2011/20120103s.pdf</a></li>
</ul>

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

CC BY-SA 4.0
2019-12-21T16:49:08.510Z
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.)
Joshua Grochow
<reference-request><complexity-classes><approximation>
If NP in BPP then NP equals RP
M.Monet
# If NP in BPP then NP equals RP

(Asked by: username_0 on 2019-12-21)

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:

* <https://cs.stackexchange.com/q/80509>
* <http://www.inf.ed.ac.uk/teaching/courses/cmc/cw3_solns.pdf>
* <https://www.csie.ntu.edu.tw/~lyuu/complexity/2011/20120103s.pdf>

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

**Tags:** reference-request, complexity-classes, approximation

> **Comments:**
> **username_1**: 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.)  

---

## 1 answers

### Answer by username_2 on 2019-12-22. Score: 11 | Accepted answer

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...)

> **Comments:**
> **username_1**: Nice - I didn't know it actually existed in the literature!  

---

