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?

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

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.

  • $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.
  • 1
    $\begingroup$ The plot thickens again! Meanwhile I'll record the page references, and note that the two articles overlap: p. 395 (p. 12 of pdf) in the first article, and p. 338 (p 25 of pdf) in the second article, which has an updated version at link.springer.com/chapter/10.1007/978-3-540-78127-1_1 $\endgroup$ – Matt F. Aug 20 '20 at 11:58
  • $\begingroup$ Thanks -- this doesn't answer the question about the paper in the question, but it is helpful. In particular, it means that each half of the theorem was discovered independently by at least three groups. $\endgroup$ – Matt F. Aug 24 '20 at 16:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.