5
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • 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$
    – Joshua Grochow
    Dec 21, 2019 at 16:49

1 Answer 1

Reset to default
11
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Nice - I didn't know it actually existed in the literature! $\endgroup$
    – Joshua Grochow
    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.