# Oracle results on P vs BPP

Let $A$ be any EXP complete problem. Then, $P^A = NP^A$.

Let $B$ be some oracle that takes into accounts the queries that $M$ (a TM in P) will make, and we can get $P^B \neq NP^B$.

Question: Do we have similar oracle results for P vs BPP?

• Yes we do, but I'm not sure I can find a citation. (Well the first part is easy, give both classes an oracle for an EXP-complete problem.) Jun 26 '12 at 4:06
• If you think of PCP setting as verifier having oracle access to prover (where the oracle query $i$ would return the $i^{th}$ bit of the proof) then we know that if you allow verifier to be a BPP machine with $\log n$ randomness and $3$ queries then the class of languages computed is $NP$ and when the verifier is a P machine (that is no randomness) with $3$ (even with $\log n$) queries then the class of languages computed is $\bf P$. This doesn't show an oracle separation unless $\bf P \neq \bf NP$. But just an example where oracle access to $\bf BPP$ "seems" more powerful. Jun 26 '12 at 15:02
• @RobinKothari Let $\oplus P=NP=EXP$ then if $A$ is any $EXP$ complete problem don't we have $NP^A=NP^{\oplus P}=\oplus P^{\oplus P}=\oplus P=NP=EXP\neq P$ (last inequality by time hierarchy)? Then does $P^A=NP^A\implies P^{\oplus P}=NP=\oplus P$ while $P\neq NP$ is shown? Nov 21 '17 at 10:59

I had a vague recollection that I knew an excellent reference for such oracle separations. I finally found it.

A great reference for oracle separations (for classes between P and PSPACE) is the following paper:

Vereshchagin, N K (1994), "RELATIVIZABLE AND NONRELATIVIZABLE THEOREMS IN THE POLYNOMIAL THEORY OF ALGORITHMS", Russian Academy of Sciences. Izvestiya Mathematics 42 (2): 261

The paper shows (or gives a citation for) an oracle separation between almost every pair of classes that you might care about between P and PSPACE (e.g., it has classes like P, RP, BPP, UP, FewP, NP, MA, AM, other levels of PH, PH, IP, PSPACE, etc.).

For example, Theorem 8 shows an oracle problem in coRP that is not in NP. Since (relative to all oracles) coRP is in BPP and NP contains P, we get an oracle problem in BPP that is not in P.

As I mentioned in my comment, showing an oracle for which $\text{P}^A = \text{BPP}^A$ is easy. Let A be a EXP-complete language or a PSPACE-complete language.

• Quite right, they only show the $BPP^{A} = P^{A}$ case. My mistake. Aug 24 '12 at 4:50