#Baker, Gill, Solovay: Relativization

The primary technical contribution of Baker, Gill, and Solovay was the construction of specific 'oracles'—external data sources that a Turing machine can consult in a single step—to show that the relationship between $P$ and $NP$ is not fixed under relativization. They proved the existence of an oracle $A$ and an oracle $B$ such that the following conflicting statements hold:

$\displaystyle P^A = NP^A \quad \text{and} \quad P^B \neq NP^B$

This finding revealed that the $P$ vs $NP$ question is 'relativization-dependent,' meaning its answer changes when the computational model is extended with an external resource. This proved that any proof technique that remains valid under an oracle (a 'relativizing' technique) is fundamentally incapable of resolving the question in the non-relativized case.

The technical significance of this result lies in its identification of the 'Diagonalization Barrier.' Before 1975, most proofs in complexity theory relied on diagonalization—a technique used by Georg Cantor to show that real numbers are uncountable and by Alan Turing to prove the Halting Problem is undecidable. Because diagonalization techniques 'relativize'—meaning they remain valid regardless of any oracle provided to the machine—BGS proved that no such technique could ever resolve P vs NP. This insight forced the community to realize that any successful proof must exploit properties of computation that do not relativize, effectively rendering the most powerful tool in the mathematician's arsenal useless for this specific problem.

Baker, Gill, and Solovay's work demonstrated that the internal logic of formal systems can be consistent with multiple, contradictory computational realities. The engineering choice to study machines with oracles proved that the P vs NP question is fundamentally different from previous challenges in logic and set theory. It suggested that progress in understanding complexity requires the discovery of 'non-relativizing' properties—characteristics of real-world circuits and algorithms that disappear when an oracle is introduced. This realization remains the primary guiding principle for researchers seeking to move beyond the structural barriers that have stalled the field for decades.