# Oracle separation P and BPP

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$$?

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$$.)