กระดาษ Baker-Gill-Solovay เป็นอย่างไร?
กระดาษ Baker-Gill-Solovay เป็นอย่างไร? เหตุใดทั้งสามคนจึงพูดคุยกันเกี่ยวกับ "Relativizations of the$P=?NP$"คำถามและความร่วมมือของพวกเขาเป็นอย่างไรสำหรับกระดาษที่ส่งเมื่อวันที่ 16 กรกฎาคม 1973?
บทความดังกล่าวได้รับการตีพิมพ์ในวารสาร SIAM Journal of Computation ในปี พ.ศ. 2518 ไม่ได้อ้างถึงงานก่อนหน้านี้ของ Ted Baker, John Gill หรือ Robert Solovay
นอกจากนี้ยังกล่าวว่าครึ่งหนึ่งของผลลัพธ์ที่มีชื่อเสียง (ทฤษฎีบท 1 คำพยากรณ์ $A$ ดังนั้น $P^A = NP^A$) "ถูกค้นพบโดยอิสระโดยอัลเบิร์ตเมเยอร์กับไมเคิลฟิสเชอร์และโดย HB Hunt III" และอีกครึ่งหนึ่ง (ทฤษฎีบท 3 คำพยากรณ์ $B$ ดังนั้น $P^B \neq NP^B$) "ได้มาโดยอิสระโดย Richard Ladner" เห็นได้ชัดว่าเราจะได้รับผลลัพธ์ BGS ในรูปแบบบางอย่างโดยไม่มีผู้แต่งชื่อสามคนใด ๆ
สิ่งที่คุ้มค่านี่คือหน้าเว็บเกี่ยวกับBaker (จากรัฐฟลอริดา), Gill (จาก Stanford) และSolovay (จาก Wikipedia) นี่คือหนังสือเกี่ยวกับJSEPซึ่งเป็นองค์กรที่ระบุว่าเป็นแหล่งเงินทุน Gill โดยมีรายละเอียดเกี่ยวกับ Stanford ในปี 1973 ในด้านกล้องจุลทรรศน์อะคูสติก แต่ไม่ใช่ในเชิงตรรกะ
โดยรวมแล้วฉันเห็นคำแนะนำทางประวัติศาสตร์เพียงเล็กน้อย แต่ผลลัพธ์ของ BGS เป็นที่ทราบกันดีว่าดูเหมือนจะคุ้มค่ากับประวัติศาสตร์สองย่อหน้าที่นี่ ใครมีข้อมูลดีๆ หรือต้องการติดต่อผู้เกี่ยวข้อง? มีเขียนเกี่ยวกับที่อื่นแล้วหรือยัง?
คำตอบ
เห็นได้ชัดว่าเราจะมีอากาศที่ครึ่งน้อย BGS ผลโดยไม่ต้องใด ๆ ในสามผู้เขียนชื่อและโดยไม่ต้องมี 4 คนที่พวกเขาเครดิตที่เราทุกคนต้องการก็คือ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) ฐานข้อมูลภายนอก