สมมติฐาน 25 ปีถูกท้าทาย หลัง OpenAI-แอนโทรปิกอ้าง AI พบวิธีแก้ 3-SAT เร็วกว่าเวลาเอ็กซ์โพเนนเชียล

โอเพนเอไอ (OpenAI) และแอนโทรปิก (Anthropic) อ้างเมื่อวันที่ 26 ตุลาคมว่าโมเดลปัญญาประดิษฐ์ (AI) ค้นพบอัลกอริทึมที่แก้ปัญหา 3-SAT ได้เร็วกว่าขอบเขตเวลาเอ็กซ์โพเนนเชียล ซึ่งอาจหักล้างสมมติฐานเวลาเอ็กซ์โพเนนเชียล ทั้งสองบริษัทเผยแพร่บทความวิจัยและบทพิสูจน์แบบเป็นทางการ

ไม่กี่วันหลังการประกาศ รัสเซลล์ อิมปาเกลียซโซ (Russell Impagliazzo) และรามาโมฮัน ปาตูรี (Ramamohan Paturi) ผู้เสนอสมมติฐานดังกล่าว รวมถึงไรอัน วิลเลียมส์ (Ryan Williams) นักวิจัยจากสถาบันเทคโนโลยีแมสซาชูเซตส์ (MIT) ซึ่งเคยตั้งข้อสงสัยต่อสมมติฐาน ให้สัมภาษณ์กับ AFP ทั้งสามแสดงความเห็นถึงความหมายของงานวิจัย การตรวจสอบโดยอิสระ และบทบาทที่ยังเหลือสำหรับนักวิจัย

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

3-SAT ที่ทั้งสองบริษัทศึกษาเป็นปัญหาว่ามีคำตอบที่ทำให้เงื่อนไขตรรกะหลายข้อเป็นจริงพร้อมกันหรือไม่ สมมติฐาน ETH ระบุว่าไม่มีอัลกอริทึมแบบกำหนดแน่นอนที่แก้ 3-SAT ได้ภายในเวลา 2^{o(n)} ในกรณีเลวร้ายที่สุด โดย n คือจำนวนตัวแปร

บทความวิจัยที่โอเพนเอไอเผยแพร่เสนออัลกอริทึมแบบกำหนดแน่นอนสำหรับนับจำนวนคำตอบของสูตรตรรกะ k-CNF อย่างแม่นยำ ร่างบทความจัดทำเมื่อวันที่ 17 ตุลาคม ส่วนฉบับแก้ไขเผยแพร่โดยระบุวันที่ 25 ตุลาคม รายชื่อผู้เขียนมีเพียงโอเพนเอไอ

แอนโทรปิกระบุว่าโมเดล Claude ที่ใช้ทำวิจัยภายในบริษัทค้นพบอัลกอริทึมที่แก้ 3-SAT ได้ในกรอบการคำนวณเชิงทฤษฎีซึ่งเร็วกว่าขอบเขตเวลาเอ็กซ์โพเนนเชียล บริษัทเผยแพร่ทั้งบทความที่ Claude เขียนและบทพิสูจน์แบบเป็นทางการใน Lean 4

ทั้งสองบริษัทจำกัดขอบเขตของผลลัพธ์ไว้ด้วย แอนโทรปิกอธิบายว่างานของบริษัทเป็นผลลัพธ์เชิงอสมมาตรที่พิจารณาปริมาณการคำนวณเมื่อขนาดปัญหาใหญ่มาก ไม่ได้หมายความว่าโมเดลจะประมวลผลปัญหาในโลกจริงได้รวดเร็ว โอเพนเอไอระบุในบทความเช่นกันว่า ผลลัพธ์นี้ไม่ได้หมายความว่าทุกปัญหาในกลุ่ม NP จะมีอัลกอริทึมที่เร็วกว่าขอบเขตเวลาเอ็กซ์โพเนนเชียล

Lean เป็นเครื่องมือที่ใช้คอมพิวเตอร์ตรวจสอบบทพิสูจน์ที่เขียนให้อยู่ในรูปแบบทางการ การที่ทั้งสองบริษัทเผยแพร่ไฟล์ Lean ทำให้ตรวจสอบได้ แต่ยังไม่ได้หมายความว่าการประเมินโดยอิสระจากแวดวงวิชาการเสร็จสิ้นแล้ว

การสัมภาษณ์เผยให้เห็นปฏิกิริยาที่ต่างกันต่อผลลัพธ์เดียวกันระหว่างผู้เสนอสมมติฐานกับนักวิจัยที่สงสัยในสมมติฐานนี้

อิมปาเกลียซโซกล่าวว่า “คงดีกว่านี้มากถ้ามนุษย์เป็นผู้ค้นพบและอธิบายกระบวนการคิดได้” เขาเสริมว่ามนุษย์อธิบายเส้นทางที่นำไปสู่คำตอบได้ และบางครั้งกระบวนการนั้นก็สำคัญไม่แพ้คำตอบ

ปาตูรีกล่าวว่าปฏิกิริยาแรกของเขาคือความประหลาดใจ พร้อมอธิบายว่าผลงานวิจัยตลอด 30 ปีที่อาศัยสมมติฐานนี้เป็นพื้นฐานไม่ได้หายไปเพียงเพราะมีการประกาศผลลัพธ์ดังกล่าว

วิลเลียมส์กล่าวว่า “ผมไม่เคยเชื่อสมมติฐานนี้อย่างเต็มที่” เขาเคยตั้งคำถามต่อสมมติฐานนี้อย่างเปิดเผย และมองว่าผลลัพธ์ครั้งนี้สนับสนุนความสงสัยของเขา

นักวิจัยทั้งสามกำลังมีส่วนร่วมจัดการตรวจสอบข้อกล่าวอ้างของสองบริษัทโดยอิสระ โอเพนเอไอระบุด้วยว่าทีมนักวิจัยภายนอกที่นำโดยอิมปาเกลียซโซ ปาตูรี และวิลเลียมส์ จะตรวจสอบบทพิสูจน์

ปาตูรีกล่าวว่าการขยายขอบเขตงานวิจัย ตลอดจนการกำหนดทิศทางและพัฒนางาน ยังคงเป็นบทบาทของมนุษย์ เขาแนะนำให้นักศึกษาเรียนรู้การใช้เครื่องมือเหล่านี้ควบคู่กับการพัฒนาวิจารณญาณของตนเอง ส่วนวิลเลียมส์กล่าวว่าสาขานี้กำลังเผชิญการเปลี่ยนแปลงครั้งใหญ่ แต่การเข้าร่วมทำวิจัยยังคุ้มค่า

อิมปาเกลียซโซกังวลว่าในตอนนี้ AI อาจรับหน้าที่แก้ปัญหาในการวิจัย ขณะที่มนุษย์ทำหน้าที่ตรวจสอบและอธิบาย เขามองว่าบทบาทดังกล่าวอาจยังเป็นของนักวิจัยมนุษย์ไปจนกว่า AI จะพัฒนาขึ้นอีก

ปาตูรีชี้ว่า หากสิทธิ์เข้าถึงเครื่องมือวิจัยที่ทรงพลังไปกระจุกตัวอยู่ในบริษัท ก็จะเกิดคำถามว่าใครได้เข้าร่วมวิจัย ใครได้ใช้เครื่องมือก่อน และใครเป็นผู้กำหนดหัวข้อวิจัย เขากล่าวว่า “การประกาศของบริษัทไม่อาจใช้แทนการประเมินโดยผู้ทรงคุณวุฒิได้” แม้ตัวย่อ ETH จะตรงกับตัวย่อของอีเธอเรียม(ETH) แต่สมมติฐานนี้ไม่เกี่ยวข้องกับอีเธอเรียม

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