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


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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.