# Why are Oracle Separations Counted as Evidence toward Unconditional Separation?

Particularly, we already have some oracle separation results such as $$\mathbf{BPP}^A\neq \mathbf{BQP}^A$$ [Simon], $$\mathbf{NP}^A\not\subseteq \mathbf{BQP}^A$$ [BBBV], and $$\mathbf{BQP}^A\not\subseteq \mathbf{NP}^A$$ [Bernstein and Vazirani]. But given that most problems are non-relativising, how does such oracle separation even counted as evidence of unconditional separation? Or do we need to discuss it case-wisely?

• Who considers it as evidence? Perhaps you should ask them. Jul 18, 2019 at 6:00
• Who are "Simon", "BBBV", and "Aaronson"? Of course, I can imagine who these people are, but what papers exactly are you referring to? Jul 18, 2019 at 7:20
• Simon's problem already yield an oracle separation between BPP and BQP, though not the first. BBBV showed the query lower bound for collision problem, which gives an oracle separation of NP from BQP as well. As for the third one, I think I might made an mistake that Bernstein and Vazirani are actually those showed oracle separation of BQP from NP using Recursive Fourier Sampling problem. Jul 18, 2019 at 14:53

It can hardly be considered evidence for inequality or equality. We know $$\mathsf{IP} = \mathsf{PSPACE}$$, but there is an oracle $$A$$ relative to which $$\mathsf{IP}^A \neq \mathsf{PSPACE}^A$$ (as proved here). Similarly, there are classes which are not equal, even though their relativized versions to a certain oracle are equal (see here for a couple examples).
The reason for all this is that, for a complexity class $$\mathsf{C}$$ (corresponding to a machine model which admits oracles) and an oracle $$O$$, $$\mathsf{C}^O$$ is potentially a different class altogether from $$\mathsf{C}$$—and it is probably best to treat it as such.
• Don't we also know oracles $A$ and $B$ such that $\mathrm{P}^A=\mathrm{NP}^A$ but $\mathrm{P}^B\neq\mathrm{NP}^B$? Jul 18, 2019 at 13:41
• @DavidRicherby That is also true, but I chose not to mention it since $\mathsf{P} = \mathsf{NP}$ is still open (and there are reputed researchers on both sides of the fence). I give examples for both equality and inequality where either case has been actually proven. Jul 18, 2019 at 14:13
• Sure. But my point is that these oracles suggest that oracle results aren't evidence on way or the other. Which ever way the $\mathrm{P}$ vs $\mathrm{NP}$ question is settled, there'll be an oracle that says the opposite. Jul 18, 2019 at 14:20
• @DavidRicherby Yes, but we already have (proven) examples which say the opposite either way. This makes the $\mathsf{P}$ and $\mathsf{NP}$ example rather superficial, at least in my POV. Jul 19, 2019 at 7:09