Как появилась статья Бейкера-Гилла-Соловея?
Как появилась статья Бейкера-Гилла-Соловея ? Почему эти трое говорили вместе о «релятивизациях$P=?NP$"Вопрос, а каково было их сотрудничество в работе над бумагой, представленной 16 июля 1973 года?"
Сама статья, опубликованная в журнале SIAM Journal of Computing 1975 года, не цитирует никаких предшествующих работ Теда Бейкера, Джона Гилла или Роберта Соловея.
Кроме того, в нем говорится, что половина известного результата (теорема 1, оракул $A$ такой, что $P^A = NP^A$) "была также независимо открыта Альбертом Мейером с Майклом Фишером и Х. Б. Хантом III", а другая половина (теорема 3, оракул $B$ такой, что $P^B \neq NP^B$) "был получен независимо Ричардом Ладнером". Очевидно, мы получили бы результат BGS в той или иной форме без какого-либо из трех названных авторов.
Вот веб-страницы о Бейкере (из штата Флорида), Гилле (из Стэнфорда) и Соловей (из Википедии). Вот книга об JSEP , организации, которая внесена в список как финансирующая Джилла, с подробностями о Стэнфорде в 1973 году в области акустической микроскопии, но не в логике.
В общем, я вижу несколько исторических намеков, но результат BGS достаточно хорошо известен, чтобы, кажется, стоить здесь пары абзацев истории. У кого-нибудь есть хорошая информация? Или хотите связаться с вовлеченными людьми? Об этом уже где-то писали?
Ответы
Очевидно, мы получили бы по крайней мере половину результата BGS без любого из трех названных авторов, а также без кого-либо из 4 человек, которых они называют, все, что нам было нужно, это Дехтияр . 😊
В Annals of the History of Computing (1984) есть исторический отчет Трахтенброта о доказательстве Дехтияра (1969), что мы можем иметь$P^A\ne NP^A$.
Трахтенброт также поясняет, что$P^A\ne NP^A (\exists A)$ Вопрос был для него главным вопросом, который они исследовали, и не рассматривался как релятивизация чего-то другого.
- $P\ne NP$ говорит, что нет способа прервать исчерпывающий поиск в математическом пространстве, определяемом входной строкой;
- $P^A\ne NP^A (\exists A)$ говорит, что нет способа сократить исчерпывающий поиск в математическом пространстве, определяемом комбинацией (i) входной строки и (ii) внешней базы данных.