4

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.

Hermann Gruber
  • 6,470
  • 1
  • 35
  • 58
rus9384
  • 355
  • 1
  • 9
  • 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. – Joshua Grochow Dec 04 '23 at 19:57

1 Answers1

5

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.

Eric Allender
  • 1,871
  • 21
  • 16