patternMinor
Why are Oracle Separations Counted as Evidence toward Unconditional Separation?
Viewed 0 times
separationswhyaretowardcountedevidenceoracleunconditionalseparation
Problem
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?
Solution
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.
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.
Context
StackExchange Computer Science Q#111945, answer score: 5
Revisions (0)
No revisions yet.