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

Question

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?

Answer 1

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.

Answer 2

Here is more about the result of M. Dekhtiar. There are several references to him proving the existence of an oracle $A$ with $P^{A} \ne NP^{A}$ (e.g. the Trakhtenbrot notes mentioned in another answer and L. Stockmeyer). His result is stated in 'On the impossibility of eliminating complete enumeration in computing a function relative to its graph', which is in Russian, and states theorems without proofs, sometimes mentioning a master’s thesis which may contain all the proofs. If this is the only source, then I can't agree that an oracle with $P^{A} \ne NP^{A}$ was found or that the work is comparable to those parts of Baker-Gill-Solovay theorem.

Briefly, Dekhtiar considered the problem of an oracle machine which has access to an unknown oracle, where we know that the oracle calculates some partial recursive function $f \colon \mathbb{N} \to \mathbb{N}$ (which can be considered in the language of function graphs as $(x, f(x))$ iff $f(x)$ is defined). Without knowledge of that oracle, we should construct the oracle Turing machine to calculate the value $f(y)$ for some input word $y$, if it is defined. The main result of Dekhtiar is proving by diagonalization over all partial recursive functions that 'the best way' is to make sequential queries to the oracle $(y, 0)$, $(y, 1)$, $(y, 2)$ ... until we either get the value of the function or loop if it is undefined. Here 'the best' means with the fewest queries to the oracle, by comparison with the whole set of possible oracles (graphs of all partial recursive functions). So,

• polynomial bounds were not considered;
• nondeterministic Turing machines were not considered;
• the only resource bound considered was the number of queries to the oracle;
• diagonalization over all partial recursive functions was used;
• the main idea was not oracle separation but a class of oracles used to show that for each ‘better machine’ we can find some oracle where it's not true (not that it will make a mistake but will use more queries).

Sometimes it is said that this work can be considered as solving $P^{A} \ne NP^{A}$ problem implicitly. For that, we would need to add polynomial bounded functions, and nondeterministic machines, which are not so hard. The proof explicitly uses estimation of the 'best machine' over all partial recursive functions, and this could be fixed with diagonalization over bounded functions. However, we can't change the formulation of the problem from Dekhtiar and it differs from the $P^{A} \ne NP^{A}$ problem. There is no trying to construct one oracle for oracle separation but only choosing for each machine another oracle to show that it's better (in some way and only for this oracle with that machine) to use exhaustive search with sequential queries.

So it sounds better to say: 'In 1969, M.Dekhtyar’ showed that nondeterminism can be more powerful than determinism if access to an oracle is allowed’, which is from J. Buss, Relativized Alternation and Space —- Bounded Computation, and sounds even better if we add “implicitly”. As Buss also said: “Independently in 1975, Baker, Gill, and Solovay exhibited oracles A, B, C, and D such that \begin{align} & P^{A} \ne NP^{A}\\ & P^{B} = NP^{B}\\ & P^{C} = NP^{C} \cap coNP^{C} \ne NP^{C}\\ & P^{D} \ne NP^{D} = coNP^{D} \end{align} They suggested that their results give evidence of the difficulty of the unrelativized $P =? NP$ problem.”