<p>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,</p>

CC BY-SA 3.0
2014-10-09T21:00:01.977Z
2014-10-09T21:00:01.977Z
Russell Impagliazzo
<p>Yes.</p>

<p>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$.</p>

<p>Consider </p>

<p>$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})$. </p>

<p>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}$.</p>

<p><strong>Update Oct 10, 2014</strong>: 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}$. </p>

<p>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 <em>any</em> 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 <em>no</em> $L_0$ realizes $\mathsf{NP}^R \neq \mathsf{P}^R$, contradicting the well-known theorem). Rather, writing it out symbolically, we've shown:</p>

<p>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$.</p>

<p>Note that, crucially, probability 1 is not the same thing as <em>all</em> $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.</p>

CC BY-SA 3.0
2014-10-08T19:01:50.740Z
The same argument applies to AM vs NP^R. Also, computability does not really matter, the only property of computable languages used in the proof is that there are countably many.
Emil Jeřábek
CC BY-SA 3.0
2014-10-08T18:23:05.917Z
2014-10-10T15:32:52.773Z
2014-10-10T15:32:52.773Z
Joshua Grochow
<p>Well, the title pretty much says it all.  The interesting question above was asked by commenter Jay on my blog (see <a href="http://www.scottaaronson.com/blog/?p=2026#comment-179120">here</a> and <a href="http://www.scottaaronson.com/blog/?p=2026#comment-179646">here</a>).  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 <i>contain</i> $BPP$.)</p>

<p>Note that I'm <i>not</i> asking about the class <a href="https://complexityzoo.uwaterloo.ca/Complexity_Zoo:A#almostp">AlmostP</a>, 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 <i>fixed</i> random oracle $R$, then in fact that language must be in $AlmostP$.</p>

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

<p>$ AM = NP^R \cap Computable.$</p>

<p>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.</p>

CC BY-SA 3.0
2014-10-09T03:33:03.700Z
There are a few related papers by Eric Allender and his coauthors: [Limits on the Computational Power of Random Strings](http://eccc.hpi-web.de/report/2010/139/), [Reductions to the Set of Random Strings: the Resource-bounded Case](http://arxiv.org/abs/1406.7658)
Kaveh
<computability><oracles><random-oracles>
For a random oracle R, does BPP equal the set of computable languages in P^R?
Scott Aaronson
# For a random oracle R, does BPP equal the set of computable languages in P^R?

(Asked by: username_0 on 2014-10-08)

Well, the title pretty much says it all. The interesting question above was asked by commenter Jay on my blog (see [here](http://www.scottaaronson.com/blog/?p=2026#comment-179120) and [here](http://www.scottaaronson.com/blog/?p=2026#comment-179646)). 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](https://complexityzoo.uwaterloo.ca/Complexity_Zoo:A#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.

**Tags:** computability, oracles, random-oracles
> **Comments:**
> **username_1**: There are a few related papers by Eric Allender and his coauthors: [Limits on the Computational Power of Random Strings](http://eccc.hpi-web.de/report/2010/139/), [Reductions to the Set of Random Strings: the Resource-bounded Case](http://arxiv.org/abs/1406.7658)  

---

## 2 answers

### Answer by username_3 on 2014-10-08. Score: 18 | Accepted answer

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.

> **Comments:**
> **username_4**: The same argument applies to AM vs NP^R. Also, computability does not really matter, the only property of computable languages used in the proof is that there are countably many.  

---

### Answer by username_2 on 2014-10-09. Score: 8

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,


---

