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 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.