The Baker-Gill-Solovay Theorem, proved by Theodore Baker, John Gill and Robert Solovay in their 1975 paper Relativizations of the P=?NP Question, shows that the P versus NP question relativizes in both directions: there is an oracle A for which P^A equals NP^A, and another oracle B for which P^B does not equal NP^B. Because most known proof techniques in complexity theory continue to work unchanged when an oracle is added, this result showed such relativizing techniques alone can never settle whether P equals NP, motivating the later search for non-relativizing methods.
Facts
StatementThere exist oracles A and B such that the complexity classes P and NP are equal relative to A but unequal relative to B. Proved by Theodore Baker, John Gill and Robert Solovay in 1975, showing that no proof technique that still works when both sides of the P versus NP question are given access to an arbitrary oracle can settle the question. 1 Classification
Statement Form Connections
Has Statement Form
Entity-backed identity for the statement-form enum value this theorem already carries, resolved to a mathematics concept by an explicit value-to-entity map (phase 3 bucket conversion, docs\design_entity_backed_browse_buckets_20260928.md). The statement-form fact itself stays on the theorem unchanged.
Sources
1. Oracle Machine (Wikipedia)
Wikimedia FoundationComplexity classes of oracle machines sectionQuote, Complexity classes of oracle machines section
Oracle machines are useful for investigating the relationship between complexity classes P and NP, by considering the relationship between PA and NPA for an oracle A. In particular, it has been shown there exist languages A and B such that PA=NPA and PB≠NPB.
Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.