# 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. – Yuval Filmus Jul 18 '19 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? – dkaeae Jul 18 '19 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. – Taylor Huang Jul 18 '19 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$? – David Richerby Jul 18 '19 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. – dkaeae Jul 18 '19 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. – David Richerby Jul 18 '19 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. – dkaeae Jul 19 '19 at 7:09