Baker-Gill-Solovay 논문은 어떻게 만들어 졌습니까?
Baker-Gill-Solovay 논문 은 어떻게 만들어 졌습니까? 왜 그 세 사람은 "의 상대화에 대해$P=?NP$"질문, 1973 년 7 월 16 일에 제출 된 논문에 대한 공동 작업은 어땠습니까?
1975 SIAM Journal of Computation에 발표 된 논문 자체는 Ted Baker, John Gill 또는 Robert Solovay의 이전 작업을 인용하지 않습니다.
또한 유명한 결과의 절반 (정리 1, 오라클은 $A$ 그런 $P^A = NP^A$) "또한 Albert Meyer와 Michael Fischer와 HB Hunt III에 의해 독립적으로 발견되었습니다.", 나머지 절반 (정리 3, 오라클 $B$ 그런 $P^B \neq NP^B$) "Richard Ladner가 독립적으로 획득했습니다". 분명히 우리는 세 명의 지명 된 저자없이 어떤 형태로 BGS 결과를 얻었을 것입니다.
그 가치에 대해서는 Baker (Florida State), Gill (Stanford) 및 Solovay (Wikipedia)에 대한 웹 페이지를 참조하십시오. 다음은 Gill에 자금을 지원하는 조직인 JSEP 에 대한 책 입니다. 1973 년 스탠포드에 대한 세부 사항은 음향 현미경 분야이지만 논리는 아닙니다.
대체로 나는 역사적 힌트를 거의 보지 못했지만 BGS 결과는 여기에서 몇 단락의 역사에 가치가있는 것으로 충분히 알려져 있습니다. 누구에게 좋은 정보가 있습니까? 아니면 관련된 사람들에게 연락하고 싶습니까? 이것은 이미 다른 곳에서 쓰여졌습니까?
답변
분명히 우리는 3 명의 지명 된 저자와 그들이 인정하는 4 명의 사람이 없이도 BGS 결과의 절반 이상을 얻었을 것 입니다. 우리가 필요로하는 것은 Dekhtiar뿐이었습니다 . 😊
컴퓨팅의 역사 실록 (1984)는이 Trakhtenbrot에 의해 역사적인 계정 우리가 할 수있는 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) 외부 데이터베이스의 조합으로 정의 된 수학적 공간을 통해 철저한 검색을 단축 할 방법이 없다고 말합니다.