Baker–Gill–Solovay theorem

Remarks

For part 1 one can take for $A$ any PSPACE-complete language, such as the true quantified Boolean formula problem. Then $\mathrm{NP}^A \subseteq \mathrm{NPSPACE} = \mathrm{PSPACE} \subseteq \mathrm{P}^A$, since a polynomial-space machine can answer the oracle queries itself. For part 2 one builds $B$ in stages by diagonalisation, so that the language $\set{1^n : B \text{ contains a string of length } n}$ is in $\mathrm{NP}^B$ but escapes each polynomial-time oracle machine in turn. A machine running in time less than $2^n$ cannot query all strings of length $n$. The construction places a string in $B$ at a length where the machine has not looked.

A proof technique relativizes when it stays valid after every machine is given the same oracle. Simulation and diagonalisation, as in the time hierarchy theorem, relativize. The theorem shows that no relativizing argument can settle the P versus NP problem, since such an argument would give the same answer for every oracle.

Going deeper

For a student

The result, from 1975, was the first of several barriers to proving separations of complexity classes. Later barriers are the natural proofs barrier of Razborov and Rudich and the algebrization barrier of Aaronson and Wigderson. Some results do not relativize: IP = PSPACE holds for real machines, but there are oracles relative to which the two classes differ. Relativized worlds remain a useful test: a proposed proof that relativizes cannot separate classes that some oracle makes equal.