Pergunta

This question already has an answer here:

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.)

Nenhuma solução correta

Licenciado em: CC-BY-SA com atribuição
Não afiliado a cs.stackexchange
scroll top