<p>It would be a <em>very</em> interesting result if one were able to present a language in BPP that is hard for RP (equivalently, for co-RP) under poly-time Turing reducibility (aka Cook reducibility).  I'm quite sure that no such language is known (natural or artificial).  If one can present such a set, then this would yield an enumeration of bounded-error probabilistic machines (BPP machines) that captures all of RP; this would be quite interesting, and I'm sure that no such enumeration is known.</p>
<p>However, note that many (perhaps most?) complexity theoreticians think that BPP = P, and thus the Circuit Value Problem is very likely hard for BPP under AC^0 reductions.</p>

CC BY-SA 4.0
2023-12-06T02:09:52.487Z
2023-12-06T02:09:52.487Z
Eric Allender
<p>It's suspected that probabilistic complexity classes such as <span class="math-container">$\mathsf{RP}$</span> or <span class="math-container">$\mathsf{BPP}$</span> don't have complete problems. Of course, their promise counterparts have complete problems, but I am not asking about promise problems. So, I have relaxed the restriction of <em>completeness</em>.</p>

CC BY-SA 4.0
2023-12-04T19:57:51.483Z
I doubt there are natural such problems known, just because we know so few natural problems in BPP \ (RP union coRP) at all (see https://cstheory.stackexchange.com/q/11425/129). But can one build such a problem unconditionally (even if "unnatural")? Interesting Q.
Joshua Grochow
<cc.complexity-theory><complexity-classes><big-picture><randomness>
Are there any problems in $\mathsf{BPP}$ that are known to be $\mathsf{RP}$-hard or $\mathsf{coRP}$-hard?
rus9384
# Are there any problems in $\mathsf{BPP}$ that are known to be $\mathsf{RP}$-hard or $\mathsf{coRP}$-hard?

(Asked by: username_0 on 2023-12-03)

It's suspected that probabilistic complexity classes such as $\mathsf{RP}$ or $\mathsf{BPP}$ don't have complete problems. Of course, their promise counterparts have complete problems, but I am not asking about promise problems. So, I have relaxed the restriction of *completeness*.

**Tags:** cc.complexity-theory, complexity-classes, big-picture, randomness

> **Comments:**
> **username_1**: I doubt there are natural such problems known, just because we know so few natural problems in BPP \ (RP union coRP) at all (see https://cstheory.stackexchange.com/q/11425/129). But can one build such a problem unconditionally (even if "unnatural")? Interesting Q.  

---

## 1 answers

### Answer by username_2 on 2023-12-06. Score: 6

It would be a *very* interesting result if one were able to present a language in BPP that is hard for RP (equivalently, for co-RP) under poly-time Turing reducibility (aka Cook reducibility). I'm quite sure that no such language is known (natural or artificial). If one can present such a set, then this would yield an enumeration of bounded-error probabilistic machines (BPP machines) that captures all of RP; this would be quite interesting, and I'm sure that no such enumeration is known.

However, note that many (perhaps most?) complexity theoreticians think that BPP = P, and thus the Circuit Value Problem is very likely hard for BPP under AC^0 reductions.


---

