โอเพนเอไอประกาศหักล้างทฤษฎีสำคัญในสาขาวิทยาการคอมพิวเตอร์ที่ใช้กันมากว่ายี่สิบปี "สมมติฐานเวลาทวีคูณ ETH"

ข่าว BlockBeats วันที่ 27 ตุลาคม OpenAI เพิ่งประกาศว่าโมเดล AI ของบริษัทสามารถ "ถอดรหัส" ETH ได้ ซึ่งเป็นข่าวที่สร้างความฮือฮาอย่างรวดเร็วในวงการเทคโนโลยีและวงการคริปโต แต่ต้องชี้แจงเป็นพิเศษว่า ETH ในที่นี้ไม่ใช่ Ethereum ซึ่งเป็นที่รู้จักกันดีในวงการคริปโตเคอร์เรนซี แต่เป็นข้อสันนิษฐานสำคัญในวิทยาการคอมพิวเตอร์ที่มีมากว่ายี่สิบปี นั่นคือ สมมติฐานเวลาทวีคูณ (Exponential Time Hypothesis หรือเรียกสั้น ๆ ว่า ETH)

คำถามหลักของสมมติฐานเวลาทวีคูณคือ ปัญหาที่ดูเหมือน "คำนวณยากเป็นพิเศษ" เหล่านั้นยากแค่ไหน?

ยกตัวอย่าง "ปัญห SAT" (ปัญหาความสามารถในการตอบสนองเชิงบูลีน) ที่บางคนอาจเคยได้ยิน ซึ่งถามว่า เมื่อให้เงื่อนไขเชิงตรรกะมาชุดหนึ่ง เราสามารถหาการกำหนดค่าแบบหนึ่งที่ทำให้เงื่อนไขทั้งหมดเป็นจริงพร้อมกันได้หรือไม่ เมื่อขนาดของปัญหาขยายใหญ่ขึ้น วิธีที่ดีที่สุดเท่าที่รู้จักในปัจจุบันโดยพื้นฐานแล้วทำได้เพียงลองคำตอบที่เป็นไปได้ทีละตัว ค่าใช้จ่ายด้านเวลาจะเพิ่มขึ้นแบบทวีคูณตามขนาด ซึ่งก็คือสิ่งที่เรียกกันว่า "เวลาทวีคูณ" นั่นเอง ETH ยังยืนยันต่อไปว่า ปัญหาประเภทนี้โดยเนื้อแท้ไม่สามารถเร่งความเร็วได้อย่างมีนัยสำคัญ และไม่มีอัลกอริทึมที่มีประสิทธิภาพในความหมายที่แท้จริงของ "เวลากึ่งทวีคูณ"

สมมติฐานนี้เป็นรากฐานสำคัญของวิทยาการคอมพิวเตอร์เชิงทฤษฎีมาตั้งแต่ถูกเสนอขึ้นในปี 1999 มีบทความหลายร้อยหลายพันชิ้นที่ใช้มันเพื่อพิสูจน์ว่า "ปัญหาบางอย่างยากมาก" หรือ "อัลกอริทึมบางตัวใกล้เคียงที่สุดแล้ว" หาก ETH ถูกหักล้างได้ ก็หมายความว่าปัญหาหลายอย่างที่เราเคยคิดว่า "แทบเป็นไปไม่ได้ที่จะเร็วขึ้น" ในทางทฤษฎีอาจมีวิธีแก้ไขที่ดีกว่า

ครั้งนี้ OpenAI อ้างว่าโมเดลของบริษัทค้นพบอัลกอริทึมแบบกำหนดได้ที่สามารถนับจำนวนคำตอบของปัญหา k-SAT ได้อย่างแม่นยำภายในเวลากึ่งทวีคูณ และได้ตรวจสอบอย่างเป็นทางการด้วย Lean หากผลลัพธ์นี้ผ่านการตรวจสอบจากผู้เชี่ยวชาญในที่สุด มันจะสั่นคลอนสมมติฐานเวลาทวีคูณโดยตรง