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$
  • 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 '19 at 16:49
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...)

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Nice - I didn't know it actually existed in the literature! $\endgroup$ – Joshua Grochow Dec 23 '19 at 4:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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