Baker-Gill-Solovayの論文はどのようにして生まれたのですか？
Baker-Gill-Solovayの論文はどのようにして生まれたのですか？なぜこれらの3人は「$P=?NP$「質問、そして1973年7月16日に提出された論文に対する彼らの協力はどのようなものでしたか？
1975年のSIAMJournal of Computationに掲載された論文自体は、Ted Baker、John Gill、RobertSolovayのいずれの以前の研究も引用していません。
さらに、それは有名な結果の半分（定理1、神託 $A$ そのような $P^A = NP^A$）「また、独立して、マイケル・フィッシャーとアルバート・マイヤーによって、そしてHBハントIIIによって発見されました」、そして残りの半分（定理3、神託 $B$ そのような $P^B \neq NP^B$）「リチャード・ラドナーが独自に入手した」。どうやら、3人の指名された著者がいなければ、何らかの形でBGSの結果が得られたはずです。
その価値については、ベイカー（フロリダ州）、ギル（スタンフォード）、ソロヴェイ（ウィキペディア）に関するWebページをご覧ください。これは、ギルに資金を提供していると記載されている組織であるJSEPに関する本で、1973年のスタンフォード大学の音響顕微鏡学の分野で詳細が説明されていますが、論理ではありません。
全体として、歴史的なヒントはほとんど見られませんが、BGSの結果は、ここで2、3段落の歴史に値するように見えることは十分に知られています。誰かが良い情報を持っていますか？または関係者に連絡したいですか？これはすでに他の場所で書かれていますか？
回答
どうやら、3人の指名された著者がいなくても、また彼らが信用している4人がいなければ、BGSの結果の少なくとも半分が得られたでしょう。必要なのはDekhtiarだけでした。😊
コンピューティングの歴史の年報（1984）には、トラクテンブロットによるDekhtiar（1969）による証明の歴史的説明があります。$P^A\ne NP^A$。
Trakhtenbrotも説明していること$P^A\ne NP^A (\exists A)$ 質問は彼にとって彼らが調査していた主な質問であり、他の何かの相対化とは見なされていませんでした。
- $P\ne NP$ 入力文字列によって定義された数学的空間を介して徹底的な検索を短絡する方法はないと言います。
- $P^A\ne NP^A (\exists A)$ （i）入力文字列と（ii）外部データベースの組み合わせによって定義される数学的空間を介して徹底的な検索を短絡する方法はないと述べています。