For a random oracle R, does BPP equal the set of computable languages in P^R?

Question

Well, the title pretty much says it all. The interesting question above was asked by commenter Jay on my blog (see here and here). I'm guessing both that the answer is yes and that there's a relatively simple proof, but I couldn't see it offhand. (Very roughly, though, one could try to show that, if a language in $P^R$ were not in $BPP$, then it must have infinite algorithmic mutual information with $R$, in which case it wouldn't be computable. Also, note that one direction is trivial: the computable languages in $P^R$ certainly contain $BPP$.)

Note that I'm not asking about the class AlmostP, which consists of those languages that are in $P^R$ for almost every $R$ (and is well-known to equal $BPP$). In this question, we first fix $R$, then look at the set of computable languages in $P^R$. On the other hand, one could try to show that, if a language in $P^R$ is computable, even for a fixed random oracle $R$, then in fact that language must be in $AlmostP$.

A closely-related question is whether, with probability 1 over a random oracle $R$, we have

$ AM = NP^R \cap Computable.$

If so, then we get the following interesting consequence: if $P=NP$, then with probability 1 over a random oracle $R$, the only languages that witness the oracle separation $P^R \ne NP^R$ are uncomputable languages.

Answer 1

Yes.

First, since it took me a minute to figure this out myself, let me formalize the difference between your question and $\mathsf{AlmostP}$; it's the order of quantifiers. $\mathsf{AlmostP} := \{L : Pr_R(L \in \mathsf{P}^R) = 1\}$, and the result you allude to is $\forall L\, L \in \mathsf{BPP} \iff Pr_R(L \in \mathsf{P}^R) = 1$. If I've understood correctly, you are asking if $Pr_R(\forall L\, L \in \mathsf{P}^R \cap \mathsf{COMP} \iff L \in \mathsf{BPP}) = Pr_R(\mathsf{P}^R \cap \mathsf{COMP} = \mathsf{BPP}) = 1$.

Consider

$p := 1-Pr_R(\mathsf{P}^R\cap \mathsf{COMP} = \mathsf{BPP}) = Pr_R(\exists L \in \mathsf{P}^R \cap \mathsf{COMP} \backslash \mathsf{BPP})$.

By the union bound, the $p$ is upper-bounded by $\sum_{L \in \mathsf{COMP}} Pr_R(L \in \mathsf{P}^R \backslash \mathsf{BPP})$. (Note that the latter sum is countable.) Now, by the 0-1 law - which applies since all the relevant statements do not change if we change $R$ finitely much - each individual probability in this sum is either 0 or 1. If the answer to your question is no, then $p=1$, so there must be some $L \in \mathsf{COMP}$ such that $Pr_R(L \in \mathsf{P}^R \backslash \mathsf{BPP}) = 1$. But this contradicts the fact that $\mathsf{AlmostP} = \mathsf{BPP}$.

Update Oct 10, 2014: As pointed out in the comment by Emil Jeřábek, the same argument applies to $\mathsf{AM}$ vs. $\mathsf{NP}^R$, since we also know that $\mathsf{AlmostNP} = \mathsf{AM}$.

He also points out that we didn't use anything about $\mathsf{COMP}$ other than that it is a countable class that contains $\mathsf{BPP}$ (resp., $\mathsf{AM}$). So the "interesting conclusion" in the OQ actually applies to any countable class of languages $\mathcal{C}$ that contains $\mathsf{AM}$: if $\mathsf{P} = \mathsf{NP}$, the "only" languages that witness the oracle separation $\mathsf{P}^R \neq \mathsf{NP}^R$ are outside of $\mathcal{C}$. But the latter statement feels somewhat misleading to me (it makes it sound like, for any $L_0$ we could consider $\mathcal{C} = \mathsf{AM} \cup \{L_0\}$, and thereby "show" that no $L_0$ realizes $\mathsf{NP}^R \neq \mathsf{P}^R$, contradicting the well-known theorem). Rather, writing it out symbolically, we've shown:

If $\mathsf{P} = \mathsf{NP}$, then $\forall \text{countable } \mathcal{C} \supseteq \mathsf{AM}\, Pr_R(\mathsf{NP}^R \neq \mathsf{P}^R \text{ and } \mathsf{NP}^R \cap \mathcal{C} = \mathsf{P}^R \cap \mathcal{C}) = 1$.

Note that, crucially, probability 1 is not the same thing as all $R$, and which full-measure set of $R$ satisfy the argument to $Pr_R$ can depend on $\mathcal{C}$. So if we try to alter $\mathcal{C}$ to $\mathcal{C} \cup \{L_0\}$, it at most removes a measure 0 set of $R$ that satisfy this statement.

Answer 2

While the order of quantifiers between what you are asking and almost P differ, it is not too hard to show that they are equivalent. First, for any fixed L, the question of whether L \in P^O does not depend on any finite initial segment of O. it follows that the probability that L \in P^R is either 0 or 1. From the almost -P result, for each computable L not in BPP, the answer is 0, while if L \in BPP, the probability is 1. Since there are countably many computable L, we can do a union bound; a countable union of probability 0 sets has probability 0. Thus, the probability that there is any computable L that is not in BPP but is in P^R is 0, as is the probability that there is a language in BPP not in P^R,