Skip to main content
1 of 2
user avatar
user avatar

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?

user44143