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
The result has influenced the development of the field by highlighting the need for non-relativizing techniques.