What are "oracle results"?

Solution 1:

Despite the odd-sounding name, oracles are indeed part of serious mathematics.

An oracle machine is a Turing machine equipped with some infinite binary string, the bits of which it can query during its operation. There are two things that I've heard the phrase "oracle result" or "oracle proof" used to describe:

The first is the use of oracle machines to prove results in computability theory. This does not mean that the oracle machine provides the proof; rather, that the proof is gotten by, among other things, proving some facts about oracle machines and then using them, that is, that oracle machines are relevant mathematical objects to the problem being solved. For example, the existence of minimal Turing degrees below $0''$ has a proof which involves proving things about certain oracle machines, as well as a proof which does not. This is not what Gasarch means, but it's worth being aware of.

The second - and relevant - meaning is, results which are relativized to an oracle. For any fixed oracle $A$, we can define the complexity classes $P^A$ and $NP^A$: $P^A$ is the class of problems solvable by a machine with $A$ as an oracle in polynomial time, and similarly for $NP^A$. Another instance of relativized definitions in complexity theory is the polynomial time hierarchy, where each successive level consists of problems solvable in polynomial time by machines given a set from the previous level as an oracle.

Now, often in computability theory, theorems relativize: if something is true about two computability-theoretic classes, it's true of those same classes relative to any oracle. For instance, it's a standard result (the Friedberg-Muchnik theorem) that there are incomparable c.e. degrees; and the proof immediately shows in fact that for any set $A$, there are incomparable degrees which are c.e. relative to $A$.

By contrast - and this is what Gasarch refers to - this kind of relativization does not tend to hold in complexity theory! In particular, Baker, Gill, and Solovay proved that:

• There is an $A$ such that $P^A=NP^A$.

• There is a $B$ such that $P^B\not=NP^B$.

So however, $P$ vs. $NP$ is resolved, the proof will have to depend specifically on the properties of the actual $P$ and $NP$; trying to relativize it to arbitrary oracles will necessarily break something.

Now, Gasarch says that this result is useful in understanding what techniques can't be used to solve $P$ vs. $NP$. The reason for this is that we can show that a number of techniques are relativizing: e.g. if you could use them to separate $P$ and $NP$ (or prove them equivalent), you could also use them to separate $P^A$ and $NP^A$ (or prove them equivalent) for any oracle $A$. By GBS, this means those proof techniques cannot be used to resolve $P$ vs. $NP$.

There are other barriers to answering $P$ vs. $NP$ as well, which are of a similar flavor - in particular, the "natural proofs" barrier of Razborov and Rudich. But the relativization barrier was the first major barrier discovered, and by far the simplest one to state and prove.