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?
Best Answer
Apparently, we would have gotten at least half of the BGS result without any of the three named authors and also without any of the 4 people they credit, all we needed was Dekhtiar. 😊
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.