4
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ I doubt there are natural such problems known, just because we know so few natural problems in BPP \ (RP union coRP) at all (see cstheory.stackexchange.com/q/11425/129). But can one build such a problem unconditionally (even if "unnatural")? Interesting Q. $\endgroup$ Dec 4, 2023 at 19:57

1 Answer 1

5
$\begingroup$

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.

$\endgroup$

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.