This famous paper proves the existence of both oracles $A$ and $B$ such that $\textbf{P}^A = \textbf{NP}^A$ and $\textbf{P}^B \neq \textbf{NP}^B$, therefore proving that any resolution to the P versus NP problem must be nontrivial in the sense that it cannot relativize.

I understand the significance of the oracle separation given by the latter oracle $B$: it shows that it certainly isn't trivially true that P = NP (of course, this result is incredibly obvious anyway!). But while I'm sure I'm wrong, the existence of the former oracle seems kind of obvious to me.

I would naively expect that for any complexity classes A and B, there would exist some oracle $O$ such that $\textbf{A}^O = \textbf{B}^O$. Just let $O$ be any oracle for a language that is complete for any complexity class C that is "sufficiently larger" than $\mathbf{A} \cup \mathbf{B}$ (in some sense which I suspect could be made precise). Then the oracle $O$ would be so much more powerful than the abstract machines whose capabilities define A and B that the most efficient solution to any tractable problem would simply be to consult the oracle and call it a day. In this case the oracle would "eat up" the original abstract machines and we would simply have $\mathbf{A}^O = \mathbf{B}^O = \mathbf{C}$. As a rather overpowered example, isn't it trivially true that $\mathbf{P}^\mathbf{R} = \mathbf{NP}^\mathbf{R} = \mathbf{R}$?

(Sorry, this question probably shows that I lack a basic conceptual understanding of how relativization works.)

  • 2
    $\begingroup$ Things are not always so simple, one example is $BPP$ and $EXP$. Following your logic (which sometimes indeed works) an oracle for say, 2EXP, should collapse the classes. However, $P^{2EXP}=BPP^{2EXP}\neq EXP^{2EXP}$. The construction which raises $BPP$ to $EXP$ is not trivial. $\endgroup$ – Ariel Jun 7 '18 at 18:17

The existence of an oracle with respect to which $\mathsf{P} = \mathsf{NP}$ shows that $\mathsf{P} \neq \mathsf{NP}$ cannot be proved using techniques that relativize such as diagonalization. In contrast, the time and space hierarchy theorems do relativize, disproving your claim that any two complexity classes are equal relative to some oracle.

The easy observation that $\mathsf{P}^\mathsf{R} = \mathsf{EXP}^\mathsf{R}$ seems to contradict the fact that the time hierarchy theorem relativizes. Tthe definition of $\mathsf{X}^\mathsf{R}$ that you use is $$ \mathsf{X}^\mathsf{R} = \bigcup_{A \in \mathsf{R}} \mathsf{X}^A.$$ The time hierarchy theorem shows that $\mathsf{P}^A \neq \mathsf{EXP}^A$ for every language $A$, but not for every family of languages.

The oracle with respect to which $\mathsf{P} = \mathsf{NP}$ is a single language. One possible choice is any $\mathsf{PSPACE}$-complete language. This is very similar to using an arbitrary recursive language, with a crucial difference – there are languages in $\mathsf{PSPACE}$ which are complete with respect to polynomial time reductions.

  • $\begingroup$ It's not completely clear how to use $\mathsf{R}$ as an oracle. Recall that an oracle is a language, not a complexity class. You need to find a problem which is $\mathsf{R}$-complete with respect to weak enough reductions. $\endgroup$ – Yuval Filmus Jun 7 '18 at 6:01
  • 1
    $\begingroup$ The time and space hierarchy theorems, however, refer to oracle Turing machines that use a single oracle. This is also the sense in which the result you are concerned about is proved. The Wikipedia definition is somewhat non-standard. $\endgroup$ – Yuval Filmus Jun 7 '18 at 19:22

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