# How did the Baker-Gill-Solovay paper come to be?

How did the Baker-Gill-Solovay paper come to be? Why were those three people talking together about "Relativizations of the $$P=?NP$$" question, and what was their collaboration like for the paper submitted July 16, 1973?

The paper itself, as published in the 1975 SIAM Journal of Computation, does not cite any prior work of any of Ted Baker, John Gill or Robert Solovay.

Furthermore, it says that half of the famous result (theorem 1, an oracle $$A$$ such that $$P^A = NP^A$$) "was also discovered, independently, by Albert Meyer with Michael Fischer and by H. B. Hunt III", and the other half (theorem 3, an oracle $$B$$ such that $$P^B \neq NP^B$$) "was obtained independently by Richard Ladner". Apparently we would have gotten the BGS result in some form without any of the three named authors.

For what it's worth, here are webpages about Baker (from Florida State), Gill (from Stanford), and Solovay (from Wikipedia). Here is a book about the JSEP, an organization listed as funding Gill, with detail on Stanford in 1973 in the area of acoustic microscopy but not in logic.

All in all I see few historical hints, but the BGS result is well-enough known to seem worth a couple paragraphs of history here. Does anyone have good information? Or want to contact the people involved? Has this been written about elsewhere already?

• @BobSolovay posts to MO sometimes. Maybe he can respond to this. – none Aug 21 '20 at 3:13

The Annals of the History of Computing (1984) has a historical account by Trakhtenbrot of the proof by Dekhtiar (1969) that we can have $$P^A\ne NP^A$$.
Trakhtenbrot also explains that the $$P^A\ne NP^A (\exists A)$$ question was for him the main question they had been investigating, and was not viewed as a relativization of something else.
• $$P\ne NP$$ says that there is no way to short-circuit an exhaustive search through a mathematical space defined by the input string;
• $$P^A\ne NP^A (\exists A)$$ says that there is no way to short-circuit an exhaustive search through a mathematical space defined by a combination of (i) the input string and (ii) an external database.