Oracle separation P and BPP

Question

I'm reading (with much pleasure) the book Quantum Computing Since Democritus by Scott Aaronson. At some point the author claims that, while most most people believe that $\mathbf{P} = \mathbf{BPP}$ in real life, it is very easy to construct an oracle $O$ such that $\mathbf{P}^O \neq \mathbf{BPP}^O$. Frankly I don't find this easy at all. Even more so I find it implausible sounding. I will explain my reasoning here.

My understanding from earlier parts of the book is that the reason people believe that $\mathbf{P} = \mathbf{BPP}$ is that we believe in the existence of good pseudo-random generators (i.e. deterministic processes that generate random looking strings) and even have some plausible looking candidate pseudo-random generators. Now whenever we want to run a $\mathbf{BPP}$ algorithm on a $\mathbf{P}$-machine we just run the algorithm as written, but replace every random bit the $\mathbf{BPP}$-machine would use by a pseudo-random bit generated by our pseudo-random generator.

You can see my problem now: we can just apply the same strategy in presence of the oracle. Whenever the $\mathbf{BPP}^O$-algorithm makes an 'ordinary' deterministic step we do the same thing in our $\mathbf{P}^O$ algorithm. Whenever the $\mathbf{BPP}^O$-algorithm queries the oracle, we query the same oracle in our $\mathbf{P}^O$ algorithm and whenever the $\mathbf{BPP}^O$-algorithm uses a random bit we use a bit from our pseudo-randomgenarator. What could go wrong, short of the oracle magically coming to life, taking physical form and smashing our pseudo-random generator with an axe? So my question is:

What is an example of an oracle $O$ such that $\mathbf{BPP}^O \neq \mathbf{P}^O$ and what problem is in the former but not the latter class?

Update: while typing a link to the following question showed up that is essentially asking the same: Existence of suitable pseudo-random number generators to derandomize BPP to P

However I don't see how the accepted answer answers my question. It seems to say that there are oracles that can distinguish the output of a given pseudo-random-generator from actually random data but

a) I can't think of a problem where having access to truly random data would give an advantage over having access to only outputs of $G$ to solve it and

b) What if the $\mathbf{P}$-machine fools the oracle by using a PRG other than $G$?

Answer 1

I'm not sure what's the simplest way, but you can use diagonalization. We will construct an oracle for the following problem: $$ L = \{ x : O(y) = 0 \text{ for all } |y|=|x| \}, $$ where $O$ is some oracle that we construct by diagonalization. The same oracle will also be used to solve $L$ in randomized polynomial time, but we will ensure that it doesn't suffice to solve $L$ in deterministic polynomial time.

Let $M_i$ be an enumeration of timed oracle Turing machines running in polytime (that is, $M_i$ runs some other machine $M'_i$ for $p_i$ time steps, where $M'_j,p_k$ go over all oracle machines and polynomials).

We construct $O$ in stages. Initially, $O$ is empty (none of its values are decided).

In stage $i$, we handle $M_i$. We pick some length $n$ on which $O$ is completely empty, and furthermore the running time of $M_i$ on $0^n$ is at most $2^{n-1}$ (this will hold for all large enough $n$), and run $M_i$ on $0^n$. Whenever $M_i$ queries an undecided value of $O$, we set the value to $0$. If the machine $M_i$ says that $0^n \notin L$, then we set all other values of $O$ of length $n$ to $0$. If it says that $0^n \in L$, then we set the other values of $O$ of length $n$ so that exactly half of them are $0$ and half of them are $1$.

Finally, we set all undecided value of $O$ (after going through the entire enumeration) to $0$.

Our construction guarantees the following properties:

• $M_i^O$ fails to compute $L$. Consequently, $L \notin \mathsf{P}^O$.
• For each length $n$, if we choose a random $y$ of length $n$ then $\Pr[O(y) = 0] \in \{1/2,1\}$. This gives a trivial random sampling algorithm for $L$, showing that $L \in \mathsf{BPP}^O$. (In fact, the algorithm has one-sided error, so $L \in \mathsf{RP}^O$.)