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.

$\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$ Commented Dec 21, 2019 at 16:49

1 Answer 1

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

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

Your Answer

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

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