BakerGillSolovay

The Baker–Gill–Solovay theorem is a foundational result in computational complexity theory, established in 1975 by Baker, Gill, and Solovay. The theorem concerns the behavior of complexity classes when computation is augmented with oracles. It states that there exist oracles A and B such that P with access to A equals NP with access to A (P^A = NP^A) and, separately, P with access to B does not equal NP with access to B (P^B ≠ NP^B). In short, relative to some oracle, P and NP can coincide; relative to another oracle, they can differ.

The significance of the Baker–Gill–Solovay theorem lies in its demonstration that relativization—a common technique in complexity theory that analyzes problems relative to oracles—cannot by itself resolve the P versus NP question. Since a single proof that P ≡ NP or P ≠ NP would have to work relative to all possible oracles, the existence of both a separating and a non-separating oracle shows that many standard, relativizing proof methods are insufficient for settling P vs NP.

The result has influenced the development of the field by highlighting the need for non-relativizing techniques. It paved the way for later advances that do not relativize, such as interactive proofs, probabilistically checkable proofs, and other non-relativizing methods that ultimately contributed to a richer understanding of complexity classes and their separations.