Как появилась статья Бейкера-Гилла-Соловея?

Aug 20 2020

Как появилась статья Бейкера-Гилла-Соловея ? Почему эти трое говорили вместе о «релятивизациях$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 достаточно хорошо известен, чтобы, кажется, стоить здесь пары абзацев истории. У кого-нибудь есть хорошая информация? Или хотите связаться с вовлеченными людьми? Об этом уже где-то писали?

Ответы

9 BjørnKjos-Hanssen Aug 20 2020 at 14:02

Очевидно, мы получили бы по крайней мере половину результата 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) внешней базы данных.