Which oracles does Relativization apply to?

Question

In 1975, Baker, Gill, and Solovay presented a landmark paper on Relativizations of the P ?= NP question.

My question is fairly simple. Does their theory hold for all oracles? I ask this because I'm not well educated on the subject. Also, I recently stumbled across some material talking about nonrelativizing oracles because they are non-recursive. I'm guessing, though, that the 1975 result is valid for all oracles. I'm basically looking for a confirmation of this, so that I can stop researching p vs. np proofs with oracles.

Answer 1

A sum over instances of $k$-SAT is not an oracle computation, if the thing you are summing, such as $1$ if a solution and $0$ if not, is computable efficiently without an oracle.

An oracle is an auxiliary black box that computes (at constant time cost per query) a particular function $f(x)$ given $x$.

Given access to an extremely powerful oracle, such as a solver for the halting problem, $P$ and $NP$ can become equivalent, because computations that used to be hard in polynomial time now become trivial, by encoding them as halting problems and asking oracle for the answer. This is the easy half of the Baker Gill Solovay theorem, where an oracle to decide all problems in PSPACE is strong enough to obliterate the difference between P and NP, because P can simulate any NP computation in polynomial space and with polynomial overhead.

The more subtle part of B-G-S is to construct an oracle that advantages NP over P to the extent that it separates the two classes when they were not known to be different (and might be the same) for computation without an oracle. For this you need an oracle that provides little information if you ask it the wrong question, and a large amount of information if you guess exactly the right question to ask, so that an NP machine gains power in ways that a P machine does not.

Answer 2

As Tsuyoshi stated the issues are not as clear cut as you may think. The relation between diagonalization and relativization is more complicated. BGS shows that there are oracles that relativized to them $\mathsf{P}$ is equal to $\mathsf{NP}$ (take any $\mathsf{PSpace\text{-}complete} problem), and there are oracles that relativized to them they are not equal (which is more complicated).

If you believe that they are not equal, then the easier results is what is useful. Since simple diagonalization arguments relativize (because they only use machines as black box, so the proof should work even if you replace them with their relativized version), you cannot separate them in the real world with a simple relativization (otherwise it would also separate them in relativized to a $\mathsf{PSpace\text{-}complete}$ oracle).

BGS result can be strengthened to: no simple diagonalization can separate $\mathsf{P}$ from $\mathsf{NP}$ (we have to define formally what it a diagonalization and when it is simple).

Informally you can think of simple diagonalization as black box separation, i.e. if the proof that there is a problem in $\mathsf{NP}$ which is not in $\mathsf{P}$ does not depend on the particular code of the machine solving that $\mathsf{NP}$ problem then the proof cannot work.

(I tried to simplify and make it easy to understand, so don't take it as completely correct. If you want to understand the details see Kozen's old paper, Fortnow's survey, and a more recent paper by Impagliazzo, Kabanets, and Kolokolova).