The reverse inclusion is obvious, as is the fact that any self-reducible NP language in BPP is also in RP. Is this also known to hold for non-self-reducible NP languages?

  • 2
    $\begingroup$ If it was known, from the inclusions $\mathbb{RP} \subseteq \mathbb{BPP}$ and $\mathbb{RP} \subseteq \mathbb{NP}$, it would follow that either $\mathbb{BPP} = \mathbb{RP}$ or $\mathbb{RP} = \mathbb{NP}$ (or both, essentially depending on the relationship between $\mathbb{BPP}$ and $\mathbb{NP}$. So I think it is safe to assume that it is currently unknown. Since $\mathbb{RP}$ has one-sided error, it is easy to see how it is contained in $\mathbb{BPP}$, without needing self-reducibility or any other property. $\endgroup$
    – chazisop
    Apr 21 '16 at 7:22
  • 4
    $\begingroup$ What is known is that $\mathrm{NP}\subseteq\mathrm{BPP}$ implies NP = RP. @chazisop, where did you get that $\mathrm{NP}\cap\mathrm{BPP}=\mathrm{RP}$ implies BPP = RP or NP = RP? $\endgroup$ Apr 21 '16 at 7:31
  • 1
    $\begingroup$ Suppose we knew $BPP \cap NP \subseteq RP (1)$. Then we can do case analysis: - If $BPP \subseteq NP$, then from (1) $NP \subseteq RP$, which with known results implies $NP = RP$. - If $NP \subseteq BPP$, then from (1) $BPP \subseteq RP$, which with known results implies $BPP = RP$. - If $NP \not\subseteq BPP$ (neither is a subset of the other), then we get $BPP \cap NP = RP$. PS: Sorry for deleting the previous comment, I accidentally posted it mid-comment and couldn't edit it to include the rest of the cases. $\endgroup$
    – chazisop
    Apr 21 '16 at 8:28
  • 4
    $\begingroup$ You got the first two cases mixed up. More importantly, in the third, generic, case, your conclusion is identical to the assumption, so the whole argument doesn't accomplish anything. In particular, it does not support the incorrect claim in your first comment. $\endgroup$ Apr 21 '16 at 9:17
  • 1
    $\begingroup$ The assumption only asks for the subset, not equality. In any case, my argument (even badly formatted and with errors), does show that if we knew what is being asked, then we could derive complexity class relations that are currently open problems. Furthermore, I fail to see how the third case if more generic than the rest: it explicitly excludes the possibility of one class containing the other, which is currently unknown. $\endgroup$
    – chazisop
    Apr 21 '16 at 9:25

As with most questions in complexity, I'm not sure there will be a full answer for a very long time. But we can at least show that the answer is non-relativizing: there is an oracle relative to which inequality holds and one relative to which equality holds. It's fairly easy to give an oracle relative to which the classes are equal: any oracle which has $\mathrm{BPP} = \mathrm{RP}$ will work (eg any oracle relative to which "randomness doesn't help much"), as will any oracle which has $\mathrm{NP} \subseteq \mathrm{BPP}$ (eg any oracle relative to which "randomness helps a lot"). There are a lot of these, so I won't bother with the specifics.

It's somewhat more challenging, though still fairly straightforward, to design an oracle relative to which we get $\mathrm{RP} \subsetneq \mathrm{BPP} \cap \mathrm{NP}$. The construction below actually does a bit better: for any constant $c$, there is an oracle relative to which there is a language in $\mathrm{coRP} \cap \mathrm{UP}$ which is not in $\mathrm{RPTIME}[2^{n^c}]$. I'll outline it below.

We'll design an oracle $A$ that contains strings of the form $(x,b,z)$, where $x$ is an $n$-bit string, $b$ is a single bit, and $z$ is a bit string of length $2n^c$. We will also give a language $L^A$ which will be decided by a $\mathrm{coRP}$ machine and a $\mathrm{UP}$ machine as follows:

  • The $\mathrm{coRP}$ machine, on input $x$, guesses $z$ of length $2|x|^c$ randomly, queries $(x,\mathtt{0},z)$, and copies the answer.
  • The $\mathrm{UP}$ machine, on input $x$, guesses $z$ of length $2|x|^c$, queries $(x,\mathtt{1},z)$, and copies the answer.

To make the above-specified machines actually meet their promises, we need $A$ to satisfy some properties. For every $x$, one of these two options must be the case:

  • Option 1: At most half of $z$ choices have $(x,\mathtt{0},z) \in A$ and zero $z$ choices have $(x,\mathtt{1},z) \in A$. (In this case, $x \not\in L^A$.)
  • Option 2: Every $z$ choice has $(x,\mathtt{0},z) \in A$ and precisely one $z$ choice has $(x,\mathtt{1},z) \in A$. (In this case, $x \in L^A$.)

Our aim will be to specify $A$ satisfying these promises so that $L^A$ diagonalizes against every $\mathrm{RPTIME}[2^{n^c}]$ machine. To try to keep this already long answer short, I'll drop the oracle construction machinery and a lot of the unimportant details, and explain how to diagonalize against a particular machine. Fix $M$ a randomized Turing machine, and let $x$ be an input so that we have full control over the selection of $b$'s and $z$'s so that $(x,b,z) \in A$. We will break $M$ on $x$.

  • Case 1: Suppose there is a way to select the $z$'s so that $A$ satisfies the first option of its promise, and $M$ has a choice of randomness which accepts. Then we will commit $A$ to this selection. Then $M$ cannot simultaneously satisfy the $\mathrm{RP}$ promise and reject $x$. Nevertheless, $x \not\in L^A$. So we have diagonalized against $M$.

  • Case 2: Next, assume that the previous case did not work out. We will now show that then $M$ can be forced either to break the $\mathrm{RP}$ promise or to reject on some choice of $A$ satisfying the second option of its promise. This diagonalizes against $M$. We will do this in two steps:

    1. Show that for every fixed choice $r$ of $M$'s random bits, $M$ must reject when all of its queries of the form $(x,\mathtt{0},z)$ are in $A$ and all of its queries of the form $(x,\mathtt{1},z)$ are not in $A$.
    2. Show that we can flip an answer $(x,\mathtt{1},z)$ of $A$ for some choice of $z$ without affecting the acceptance probability of $M$ by much.

    Indeed, if we start with $A$ from step 1, $M$'s acceptance probability is zero. $A$ doesn't quite satisfy the second option of its promise, but we can then flip a single bit as in step 2 and it will. Since flipping the bit causes $M$'s acceptance probability to stay near zero, it follows that $M$ cannot simultaneously accept $x$ and satisfy the $\mathrm{RP}$ promise.

It remains to argue the two steps in Case 2:

  1. Fix a choice of random bits $r$ for $M$. Now simulate $M$ using $r$ as the randomness and answering the queries so that $(x,\mathtt{0},z) \in A$ and $(x,\mathtt{1},z) \not\in A$. Observe that $M$ makes at most $2^{n^c}$ queries. Since there are $2^{2n^c}$ choices of $z$, we can fix the unqueried choices of $z$ to have $(x,\mathtt{0},z) \not\in A$, and have $A$ still satisfy the first option of its promise. Since we couldn't make Case 2 work for $M$, this means $M$ must reject on all its choices of randomness relative to $A$, and in particular on $r$. It follows that if we select $A$ to have $(x,\mathtt{0},z) \in A$ and $(x,\mathtt{1},z) \not\in A$ for every choice of $z$, then for every choice of random bits $r$, $M$ rejects relative to $A$.

  2. Suppose that for every $z$, the fraction of random bits for which $M$ queries $(x,\mathtt{1},z)$ is at least $1/2$. Then the total number of queries is at least $2^{2n^c} 2^{2^{n^c}}/2$. On the other hand, $M$ makes at most $2^{2^{n^c}} 2^{n^c}$ queries across all its branches, a contradiction. Hence there is a choice of $z$ so that the fraction of random bits for which $M$ queries $(x,\mathtt{1},z)$ is less than 1/2. Flipping the value of $A$ on this string therefore affects the acceptance probability of $M$ by less than $1/2$.

  • $\begingroup$ This answer is fairly long and would probably benefit from a link to an outside resource that gives a better explanation of the techniques involved. If anyone knows of one, I'll happily include it. $\endgroup$ Apr 27 '16 at 17:20
  • $\begingroup$ It might be in Ko's survey. $\endgroup$
    – Kaveh
    Apr 27 '16 at 18:00
  • 1
    $\begingroup$ @Kaveh: I looked at this survey (it's the one you're referring to, right?), but I didn't notice much that seems immediately relevant. Most of the results seemed like they would fall into the case of proving $\mathrm{BPP} \cap \mathrm{NP} = \mathrm{RP}$. One notable point is that $\mathrm{P} = \mathrm{RP}$ relative to a random oracle, and so we get $\mathrm{BPP} \cap \mathrm{NP} = \mathrm{RP}$ relative to a random oracle. $\endgroup$ Apr 27 '16 at 21:32

No, it's not known. This might not be the most convincing proof, but take a look at this Google search.


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.