OpenAI และ Anthropic ต่างก็เผยแพร่บทพิสูจน์ว่าสมมติฐานเวลาเอ็กซ์โปเนนเชียลเป็นเท็จ
ETH เป็นข้อสมมติฐานอายุ 27 ปีในสาขาวิทยาการคอมพิวเตอร์เชิงทฤษฎีที่ระบุว่าบางปัญหาไม่สามารถแก้ได้เร็วไปกว่าการลองผิดลองถูกแบบครอบคลุมอย่างมีนัยสำคัญ ตอนนี้ ห้องปฏิบัติการ AI ชั้นนำบอกว่านั่นไม่จริง
หากบทพิสูจน์ยืนหยัดได้ นี่จะเป็นผลลัพธ์ที่ AI สร้างขึ้นซึ่งสำคัญที่สุดในวิทยาการคอมพิวเตอร์จนถึงปัจจุบัน และยังบังคับให้ต้องทบทวนงานวิจัยนับร้อยฉบับที่ตั้งอยู่บนสมมติฐานว่า ETH เป็นจริง
ในบทความนี้ จะอธิบายว่าแท้จริงแล้วสมมติฐานเวลาเอ็กซ์โปเนนเชียลหมายความว่าอย่างไร พร้อมกับ P เทียบกับ NP ซึ่งเกี่ยวข้องกัน นอกจากนี้จะพิจารณาด้วยว่าแต่ละห้องปฏิบัติการอ้างอะไร ตรวจสอบบทพิสูจน์อย่างไร และอะไรที่เปลี่ยน (และไม่เปลี่ยน) สำหรับวิทยาการเข้ารหัส
P เทียบกับ NP แบบเข้าใจง่าย
P เทียบกับ NP ถามว่าทุกปัญหาที่คำตอบตรวจสอบได้ง่ายนั้น แก้ได้ง่ายด้วยหรือไม่ นี่เป็นหนึ่งในปัญหา Millennium Prize ทั้งเจ็ดข้อ และยังคงเปิดอยู่หลังข่าวนี้
ซูโดกุเป็นตัวอย่างคลาสสิก การตรวจสอบกระดานที่เติมตัวเลขแล้วใช้เวลาเพียงไม่กี่วินาที: ไล่ดูแต่ละแถว คอลัมน์ และบล็อกว่ามีตัวเลขซ้ำหรือไม่ การหาคำตอบจากกระดานที่ยังว่างอยู่มากอาจใช้เวลานานกว่ามาก และช่องว่างนี้จะขยายตัวอย่างรุนแรงเมื่อขนาดกระดานใหญ่ขึ้น
- P คือกลุ่มของปัญหาที่คอมพิวเตอร์สามารถแก้ได้ในเวลาโพลีโนเมียล หมายความว่า ปริมาณงานเติบโตตาม n2, n3 เป็นต้น เมื่อขนาดอินพุต n เพิ่มขึ้น
- NP คือกลุ่มของปัญหาที่คอมพิวเตอร์สามารถยืนยันคำตอบที่เสนอมาได้ในเวลาโพลีโนเมียล
ทุกปัญหาใน P อยู่ใน NP ด้วย คำถามที่ยังเปิดอยู่คือส่วนกลับเป็นจริงหรือไม่ นักวิทยาการคอมพิวเตอร์ส่วนใหญ่เชื่อว่า P ≠ NP ดังนั้นบางปัญหาจึงยากกว่ามากในการแก้ให้ได้คำตอบ มากกว่าการตรวจว่าคำตอบถูกต้องหรือไม่ วิทยาการเข้ารหัสสมัยใหม่อาศัยความเชื่อนี้: การเข้ารหัสทำได้ง่าย แต่การถอดรหัสโดยไม่มีคีย์ควรยาก
สมมติฐานเวลาเอ็กซ์โปเนนเชียลคืออะไร?
ETH เฉียบคมกว่านั้น: มันอ้างว่าปัญหา NP เฉพาะหนึ่งปัญหา คือ 3-SAT ต้องใช้เวลาเอ็กซ์โปเนนเชียลไม่ว่าจะมีอัลกอริทึมฉลาดแค่ไหน Russell Impagliazzo และ Ramamohan Paturi จาก UC San Diego เสนอไว้ในปลายทศวรรษ 1990 โดยมี Francis Zane มีส่วนร่วมในงานรากฐาน
ปัญหา 3-SAT
ใน 3-SAT จะได้รับสูตรที่ประกอบด้วยตัวแปรจริง/เท็จ n ตัว และรายการของคลอส แต่ละคลอสเชื่อมเงื่อนไขสามข้อด้วย OR ตัวอย่างเช่น "x₁ เป็นจริง หรือ x₄ เป็นเท็จ หรือ x₇ เป็นจริง" งานคือหาค่าของตัวแปรที่ทำให้ทุกคลอสเป็นจริงพร้อมกัน
การลองผิดลองถูกแบบครอบคลุมจะลองค่าทั้งหมด 2ⁿ ดังนั้นตัวแปรเพิ่มทีละตัว งานก็เพิ่มเป็นสองเท่า จะเห็นได้ว่าประมาณ 100 ตัวแปรขึ้นไปแทบเป็นไปไม่ได้
ETH พูดว่าอะไร
ETH ระบุว่ามีค่าคงที่ c > 1 บางค่า ที่ทำให้อัลกอริทึมใด ๆ ก็ไม่สามารถแก้ 3-SAT ได้เร็วกว่า cⁿ อัลกอริทึมที่ฉลาดสามารถลดฐานลงต่ำกว่า 2 ได้ แต่ไม่มีทางลดลงไปถึงระดับที่ต่ำกว่าเอ็กซ์โปเนนเชียลอย่างแท้จริง ในรูปแบบทางการ: มีอยู่ของ δ > 0 ที่ทำให้ 3-SAT ไม่สามารถแก้ได้ในเวลา O(2δn)
ตลอดหลายทศวรรษ ความก้าวหน้าก็สอดคล้องกับภาพนั้น นักวิจัยค่อย ๆ โกนค่าฐานลง แต่ก็ยังสูงกว่า 1 อยู่มาก และเพราะ 3-SAT สามารถแปลงไปเป็นปัญหาอื่น ๆ ได้มากมาย ETH จึงกลายเป็นสมมติฐานหลัก นักวิจัยใช้มันเพื่อโต้แย้งว่าปัญหาอย่าง Clique, Vertex Cover, Independent Set และอื่น ๆ ก็ไม่สามารถแก้ได้เร็วขึ้นมากเช่นกัน
ผลลัพธ์ใหม่เปรียบเทียบอย่างไร
| วิธีการ | เวลาในการทำงานสำหรับ 3-SAT | เติบโตแบบเอ็กซ์โปเนนเชียลหรือไม่ |
|---|
| ลองผิดลองถูกแบบครอบคลุม | 2ⁿ | ใช่ |
| ดีที่สุดก่อน ต.ค. 2026 (กำหนดแน่) | ประมาณ 1.328ⁿ | ใช่ |
| ดีที่สุดก่อน ต.ค. 2026 (สุ่ม) | ประมาณ 1.308ⁿ | ใช่ |
| OpenAI และ Anthropic (ต.ค. 2026) | 2^O(n log log n / √log n) | ไม่: ต่ำกว่าเอ็กซ์โปเนนเชียล |
ขอบเขตใหม่เขียนย่อว่า 2o(n) ต้นทุนต่อการเพิ่มตัวแปรหนึ่งตัวจะหดเข้าใกล้ 1 เมื่อ n โตขึ้น ซึ่งเป็นสิ่งที่ ETH บอกว่าเป็นไปไม่ได้พอดี
OpenAI และ Anthropic ประกาศอะไร
ทั้งสองห้องปฏิบัติการได้ขอบเขตต่ำกว่าเอ็กซ์โปเนนเชียลที่แทบเหมือนกันโดยอิสระจากกัน และทั้งคู่หนุนบทความด้วยบทพิสูจน์ที่ตรวจสอบด้วยเครื่องในตัวช่วยพิสูจน์ Lean
| | OpenAI | Anthropic |
|---|
| บทความ | "The Exponential Time Hypothesis Is False" (67 หน้า) | "A 2o(n) Time Algorithm for 3-SAT" (49 หน้า) |
| โมเดล | โมเดลภายในที่ไม่ระบุชื่อ | โมเดลวิจัย Claude ภายใน ระบุชื่อเป็นผู้เขียน |
| พบไอเดียหลัก | 16 ตุลาคม 2026 | 16 ตุลาคม 2026 |
| เผยต่อสาธารณะ | 26 ตุลาคม 2026 | 26–27 ตุลาคม 2026 |
| การตรวจสอบ | บทพิสูจน์ใน Lean สำหรับขอบเขตที่อ่อนกว่านิดหน่อยแต่ยังหักล้าง ETH ได้ | บทพิสูจน์ Lean 4 บน Mathlib ตรวจซ้ำด้วยเคอร์เนลที่สอง |
| ข้ออ้างเพิ่มเติม | ความเร็วที่ได้ไม่ขยายไปยังทั้งกลุ่ม NP | หักล้าง SETH ด้วย; มีขอบเขตล่างของวงจรใหม่ |
Anthropic ระบุว่า Claude พบอัลกอริทึมแกนกลางโดยไม่มีอินพุตจากมนุษย์หลังจากสร้างเอาต์พุตราว 14 ล้านโทเคน วิธีการนี้ใช้เครือข่ายเทนเซอร์และอาร์กิวเมนต์เชิงอันดับ จากนั้นนักวิจัยช่วยทำบทความฉบับสมบูรณ์
ทำไมทั้งสองห้องปฏิบัติการถึงค้นพบในวันเดียวกัน?
ยังไม่มีห้องปฏิบัติการใดอธิบายเรื่องจังหวะเวลา บทความของ Anthropic ระบุว่าผลลัพธ์ทั้งสองเป็นอิสระและเกิดพร้อมกัน และงานเขียนทั้งสองเดินผ่านคณิตศาสตร์คนละเส้นทางเพื่อไปถึงขอบเขตแทบเหมือนกัน
บริบทบางอย่างทำให้ความซ้ำซ้อนไม่น่าประหลาดใจเท่าที่เห็นครั้งแรก ทั้งสองห้องปฏิบัติการส่งโมเดลของตนไปยังรายการปัญหาเปิดยาวเหยียด และ OpenAI เพียงรายเดียวก็ปล่อยต้นฉบับงานคณิตศาสตร์ที่ AI สร้างขึ้นหลายร้อยฉบับเมื่อต้นตุลาคม ETH เป็นหนึ่งในเป้าหมายที่รู้จักกันดีที่สุดในสาขานี้ และทั้งสองโมเดลก็เรียนรู้จากงานวิจัยที่ตีพิมพ์ชุดเดียวกัน การค้นพบอิสระพร้อมกันยังเป็นรูปแบบเก่าแก่ในวิทยาศาสตร์ เช่น นิวตันกับไลบ์นิซเรื่องแคลคูลัส หรือดาร์วินกับวอลเลซเรื่องการคัดเลือกโดยธรรมชาติ
บทพิสูจน์แน่นแค่ไหน
Lean ยืนยันว่าข้อความทางการตามตรรกะจากสัจพจน์ของมัน แต่ไม่สามารถยืนยันได้ว่าข้อความทางการนั้นสื่อสารสิ่งเดียวกับบทความหรือไม่ Anthropic ชี้ว่าไม่มีเครื่องมือใดตรวจสอบการจับคู่นี้ และ OpenAI ระบุว่าไฟล์ Lean ของตนพิสูจน์ขอบเขตที่อ่อนกว่าพาดหัวเล็กน้อย
ตอนนี้ นักวิจัยกลุ่มเดียวกับที่เสนอปัญหา Impagliazzo และ Paturi พร้อมด้วย Ryan Williams จาก MIT กำลังจัดเวิร์กช็อปเพื่อประเมินว่าข้อความทางการนั้นสะท้อน ETH อย่างแท้จริงหรือไม่ จดหมายของพวกเขาเน้นว่าการเข้าร่วมการทบทวนไม่ได้เท่ากับการรับรอง ขณะที่กำลังเขียนบทความนี้ ยังไม่มีใครพบข้อบกพร่องต่อสาธารณะ
Williams กล่าวว่าส่วนหนึ่งของบทพิสูจน์ของ OpenAI ดูเป็นเรื่องปกติ ในขณะที่ "สองหรือสามส่วนที่ดูประหลาด" ยังต้องพิจารณาอย่างเข้มงวด Impagliazzo หนึ่งในผู้เขียน ETH บรรยายผลลัพธ์นี้ว่าน่าประหลาดใจอย่างลึกซึ้ง
อะไรเปลี่ยนและอะไรไม่เปลี่ยน
ในทางปฏิบัติ แทบไม่มีอะไรเปลี่ยนวันนี้ (โล่งอก): อัลกอริทึมใหม่ชนะการลองผิดลองถูกเฉพาะบนอินพุตที่ใหญ่กว่าขนาดที่คอมพิวเตอร์ใด ๆ จะเก็บได้อย่างเทียบไม่ได้
ไม่มีตัวแก้ SAT ที่เร็วขึ้น
บทความของ Anthropic ระบุว่าวิธีการของตนชนะการลองผิดลองถูกเฉพาะบนอินพุตที่ใหญ่แบบมหาศาล สำหรับสูตรทั่วไปที่มีห้าคลอสต่อหนึ่งตัวแปร จุดตัดกันอยู่ที่ตัวเลขที่มีประมาณ 10,000 หลัก ในกรณีทั่วไปที่สุด จะเป็นตัวเลขที่มีราว ๆ 100 ล้านหลัก
ผู้เขียนยังระบุด้วยว่าวิธีของตนไม่น่าจะช่วยอะไรได้กับอินพุตต่ำกว่าประมาณ 10 ล้านตัวแปร ตัวแก้ SAT ที่ใช้ในการตรวจสอบชิป การจัดตารางงาน และการวางแผนจะไม่เร็วขึ้นจากผลลัพธ์นี้
วิทยาการเข้ารหัสไม่พัง
ผลลัพธ์นี้ไม่แตะต้อง P เทียบกับ NP ไม่มีใครอ้างเช่นนั้น OpenAI ระบุว่าได้ตรวจแล้วว่าอัลกอริทึมไม่ทำลายระบบเข้ารหัสจริง และค่อนข้างมั่นใจว่าไม่ทำ
ทฤษฎีต้องเขียนใหม่
ผลกระทบที่ใหญ่กว่าอยู่ที่งานวิจัย ผลลัพธ์ด้านความยากที่สร้างบน ETH หรือ SETH ตอนนี้ต้องหาหลักฐานใหม่ และนักวิจัยบางคนกล่าวว่างานของตนหลายปีอาจต้องทบทวน อย่างไรก็ดี ไม่ได้มีทุกอย่างที่พังลง Anthropic ชี้ว่าผลลัพธ์นี้ไม่ได้หักล้าง ปัญหาเวกเตอร์ตั้งฉาก ซึ่งรองรับผลลัพธ์ด้านความซับซ้อนแบบละเอียดจำนวนมาก
ทำไมจึงสำคัญต่อ AI
พาดหัวข่าวไม่ใช่เรื่อง 3-SAT เท่านั้น แต่คือผู้ที่ค้นพบคำตอบ: สองระบบ AI หักล้างข้อคาดการณ์ที่ผู้เชี่ยวชาญมนุษย์เชื่อถือกันมานานหลายรุ่น โดยอิสระจากกัน
AI ในฐานะผู้ร่วมวิจัย
นักวิจัยบรรยายว่าตอนนี้มีผลลัพธ์ AI ใหม่ ๆ ออกมาทุกสัปดาห์หรือสองสัปดาห์ ทำให้โครงการที่ทำอยู่ถูกรบกวน เครื่องมือเชิงรูปแบบอย่าง Lean กำลังกลายเป็นศูนย์กลาง เพราะช่วยให้มนุษย์ไว้ใจบทพิสูจน์ที่ยาวและเขียนโดยเครื่องได้โดยไม่ต้องอนุมานซ้ำทุกบรรทัด
ทางลัดที่ซ่อนอยู่และการพัฒนาตนเอง
ETH จับความเชื่อที่ว่าบางปัญหาการค้นหาไม่มีทางลัดที่ฉลาด หากความเชื่อนี้ผิด ปัญหาอื่น ๆ ที่ดูยากอย่างชัดเจนอาจซ่อนทางลัดไว้เช่นกัน
กำลังคิดถึงการค้นพบอัลกอริทึมว่าเป็นหนึ่งในพื้นที่ที่ทางลัดดังกล่าวอาจสำคัญมากต่อ การพัฒนาตนเองแบบเวียนเกิด ซึ่งเป็นแนวคิดของระบบ AI ที่ช่วยออกแบบ AI ที่ดีกว่า การใช้งาน AI เพื่อค้นหาอัลกอริทึมที่เร็วขึ้นเป็นหนึ่งในเส้นทางที่เป็นรูปธรรม แม้ว่าไม่มีอะไรในผลลัพธ์นี้จะทำเช่นนั้นได้โดยตรงในวันนี้
หมายความว่าอย่างไรสำหรับผู้ทำงานกับข้อมูล
สำหรับผู้ที่สร้างงานด้วยข้อมูล มีสามบทเรียนที่โดดเด่น:
- ทฤษฎีความซับซ้อนไม่ได้เป็นเรื่องวิชาการล้วน: การรู้ว่าทำไมปัญหาจึงเป็น NP-hard บอกได้ว่าเมื่อไรควรคิดถึงฮิวริสติก การประมาณ หรือซอลเวอร์ แทนการค้นหาคำตอบแบบตรงตัว
- การตรวจสอบคือทักษะ: เมื่อ AI สร้างโค้ดและการวิเคราะห์มากขึ้น การตรวจเอาต์พุต (ด้วยการทดสอบ บทพิสูจน์ หรือไปป์ไลน์ที่ทำซ้ำได้) สำคัญพอ ๆ กับการสร้างมัน
- แอสซิมพ์โตติกอาจทำให้หลงทาง: อัลกอริทึมที่ “เร็วกว่า” ในทฤษฎีอาจไร้ประโยชน์ในขนาดที่พบจริง
บทสรุป
หากบทพิสูจน์ผ่านการทบทวนจากผู้เชี่ยวชาญ สมมติฐานเวลาเอ็กซ์โปเนนเชียลจะเข้าร่วมรายการสั้น ๆ ของข้อคาดการณ์ที่เชื่อกันอย่างกว้างขวางแต่กลายเป็นเท็จ (เช่น ข้อคาดการณ์ผลบวกกำลังของออยเลอร์) แต่ P เทียบกับ NP ยังคงเปิดอยู่ และวิทยาการเข้ารหัสยังปลอดภัยในตอนนี้
หมุดหมายถัดไปที่ควรจับตาคือเวิร์กช็อปการทบทวนที่นำโดยผู้เขียนดั้งเดิมของ ETH การนำอัลกอริทึมกลับมาทำซ้ำโดยอิสระ และดูว่ามีใครทำให้ขอบเขตแน่นขึ้นอีกหรือไม่
เพื่อสร้างรากฐานเบื้องหลังเรื่องราวแบบนี้ ลองสำรวจคอร์สของเราเกี่ยวกับโครงสร้างข้อมูลและอัลกอริทึม, การเขียนโปรแกรม Python และการเรียนรู้ของเครื่อง ซึ่งครอบคลุมแนวคิด Big-O ที่ทำให้ผลลัพธ์แบบนี้อ่านเข้าใจได้
OpenAI และ Anthropic ต่างก็เผยแพร่บทพิสูจน์ว่าสมมติฐานเวลาเอ็กซ์โปเนนเชียลเป็นเท็จ
ETH เป็นข้อสมมติฐานอายุ 27 ปีในสาขาวิทยาการคอมพิวเตอร์เชิงทฤษฎีที่ระบุว่าบางปัญหาไม่สามารถแก้ได้เร็วไปกว่าการลองผิดลองถูกแบบครอบคลุมอย่างมีนัยสำคัญ ตอนนี้ ห้องปฏิบัติการ AI ชั้นนำบอกว่านั่นไม่จริง
หากบทพิสูจน์ยืนหยัดได้ นี่จะเป็นผลลัพธ์ที่ AI สร้างขึ้นซึ่งสำคัญที่สุดในวิทยาการคอมพิวเตอร์จนถึงปัจจุบัน และยังบังคับให้ต้องทบทวนงานวิจัยนับร้อยฉบับที่ตั้งอยู่บนสมมติฐานว่า ETH เป็นจริง
ในบทความนี้ จะอธิบายว่าแท้จริงแล้วสมมติฐานเวลาเอ็กซ์โปเนนเชียลหมายความว่าอย่างไร พร้อมกับ P เทียบกับ NP ซึ่งเกี่ยวข้องกัน นอกจากนี้จะพิจารณาด้วยว่าแต่ละห้องปฏิบัติการอ้างอะไร ตรวจสอบบทพิสูจน์อย่างไร และอะไรที่เปลี่ยน (และไม่เปลี่ยน) สำหรับวิทยาการเข้ารหัส
P เทียบกับ NP แบบเข้าใจง่าย
P เทียบกับ NP ถามว่าทุกปัญหาที่คำตอบตรวจสอบได้ง่ายนั้น แก้ได้ง่ายด้วยหรือไม่ นี่เป็นหนึ่งในปัญหา Millennium Prize ทั้งเจ็ดข้อ และยังคงเปิดอยู่หลังข่าวนี้
ซูโดกุเป็นตัวอย่างคลาสสิก การตรวจสอบกระดานที่เติมตัวเลขแล้วใช้เวลาเพียงไม่กี่วินาที: ไล่ดูแต่ละแถว คอลัมน์ และบล็อกว่ามีตัวเลขซ้ำหรือไม่ การหาคำตอบจากกระดานที่ยังว่างอยู่มากอาจใช้เวลานานกว่ามาก และช่องว่างนี้จะขยายตัวอย่างรุนแรงเมื่อขนาดกระดานใหญ่ขึ้น
ทุกปัญหาใน P อยู่ใน NP ด้วย คำถามที่ยังเปิดอยู่คือส่วนกลับเป็นจริงหรือไม่ นักวิทยาการคอมพิวเตอร์ส่วนใหญ่เชื่อว่า P ≠ NP ดังนั้นบางปัญหาจึงยากกว่ามากในการแก้ให้ได้คำตอบ มากกว่าการตรวจว่าคำตอบถูกต้องหรือไม่ วิทยาการเข้ารหัสสมัยใหม่อาศัยความเชื่อนี้: การเข้ารหัสทำได้ง่าย แต่การถอดรหัสโดยไม่มีคีย์ควรยาก
สมมติฐานเวลาเอ็กซ์โปเนนเชียลคืออะไร?
ETH เฉียบคมกว่านั้น: มันอ้างว่าปัญหา NP เฉพาะหนึ่งปัญหา คือ 3-SAT ต้องใช้เวลาเอ็กซ์โปเนนเชียลไม่ว่าจะมีอัลกอริทึมฉลาดแค่ไหน Russell Impagliazzo และ Ramamohan Paturi จาก UC San Diego เสนอไว้ในปลายทศวรรษ 1990 โดยมี Francis Zane มีส่วนร่วมในงานรากฐาน
ปัญหา 3-SAT
ใน 3-SAT จะได้รับสูตรที่ประกอบด้วยตัวแปรจริง/เท็จ n ตัว และรายการของคลอส แต่ละคลอสเชื่อมเงื่อนไขสามข้อด้วย OR ตัวอย่างเช่น "x₁ เป็นจริง หรือ x₄ เป็นเท็จ หรือ x₇ เป็นจริง" งานคือหาค่าของตัวแปรที่ทำให้ทุกคลอสเป็นจริงพร้อมกัน
การลองผิดลองถูกแบบครอบคลุมจะลองค่าทั้งหมด 2ⁿ ดังนั้นตัวแปรเพิ่มทีละตัว งานก็เพิ่มเป็นสองเท่า จะเห็นได้ว่าประมาณ 100 ตัวแปรขึ้นไปแทบเป็นไปไม่ได้
ETH พูดว่าอะไร
ETH ระบุว่ามีค่าคงที่ c > 1 บางค่า ที่ทำให้อัลกอริทึมใด ๆ ก็ไม่สามารถแก้ 3-SAT ได้เร็วกว่า cⁿ อัลกอริทึมที่ฉลาดสามารถลดฐานลงต่ำกว่า 2 ได้ แต่ไม่มีทางลดลงไปถึงระดับที่ต่ำกว่าเอ็กซ์โปเนนเชียลอย่างแท้จริง ในรูปแบบทางการ: มีอยู่ของ δ > 0 ที่ทำให้ 3-SAT ไม่สามารถแก้ได้ในเวลา O(2δn)
ตลอดหลายทศวรรษ ความก้าวหน้าก็สอดคล้องกับภาพนั้น นักวิจัยค่อย ๆ โกนค่าฐานลง แต่ก็ยังสูงกว่า 1 อยู่มาก และเพราะ 3-SAT สามารถแปลงไปเป็นปัญหาอื่น ๆ ได้มากมาย ETH จึงกลายเป็นสมมติฐานหลัก นักวิจัยใช้มันเพื่อโต้แย้งว่าปัญหาอย่าง Clique, Vertex Cover, Independent Set และอื่น ๆ ก็ไม่สามารถแก้ได้เร็วขึ้นมากเช่นกัน
ผลลัพธ์ใหม่เปรียบเทียบอย่างไร
ขอบเขตใหม่เขียนย่อว่า 2o(n) ต้นทุนต่อการเพิ่มตัวแปรหนึ่งตัวจะหดเข้าใกล้ 1 เมื่อ n โตขึ้น ซึ่งเป็นสิ่งที่ ETH บอกว่าเป็นไปไม่ได้พอดี
OpenAI และ Anthropic ประกาศอะไร
ทั้งสองห้องปฏิบัติการได้ขอบเขตต่ำกว่าเอ็กซ์โปเนนเชียลที่แทบเหมือนกันโดยอิสระจากกัน และทั้งคู่หนุนบทความด้วยบทพิสูจน์ที่ตรวจสอบด้วยเครื่องในตัวช่วยพิสูจน์ Lean
Anthropic ระบุว่า Claude พบอัลกอริทึมแกนกลางโดยไม่มีอินพุตจากมนุษย์หลังจากสร้างเอาต์พุตราว 14 ล้านโทเคน วิธีการนี้ใช้เครือข่ายเทนเซอร์และอาร์กิวเมนต์เชิงอันดับ จากนั้นนักวิจัยช่วยทำบทความฉบับสมบูรณ์
ทำไมทั้งสองห้องปฏิบัติการถึงค้นพบในวันเดียวกัน?
ยังไม่มีห้องปฏิบัติการใดอธิบายเรื่องจังหวะเวลา บทความของ Anthropic ระบุว่าผลลัพธ์ทั้งสองเป็นอิสระและเกิดพร้อมกัน และงานเขียนทั้งสองเดินผ่านคณิตศาสตร์คนละเส้นทางเพื่อไปถึงขอบเขตแทบเหมือนกัน
บริบทบางอย่างทำให้ความซ้ำซ้อนไม่น่าประหลาดใจเท่าที่เห็นครั้งแรก ทั้งสองห้องปฏิบัติการส่งโมเดลของตนไปยังรายการปัญหาเปิดยาวเหยียด และ OpenAI เพียงรายเดียวก็ปล่อยต้นฉบับงานคณิตศาสตร์ที่ AI สร้างขึ้นหลายร้อยฉบับเมื่อต้นตุลาคม ETH เป็นหนึ่งในเป้าหมายที่รู้จักกันดีที่สุดในสาขานี้ และทั้งสองโมเดลก็เรียนรู้จากงานวิจัยที่ตีพิมพ์ชุดเดียวกัน การค้นพบอิสระพร้อมกันยังเป็นรูปแบบเก่าแก่ในวิทยาศาสตร์ เช่น นิวตันกับไลบ์นิซเรื่องแคลคูลัส หรือดาร์วินกับวอลเลซเรื่องการคัดเลือกโดยธรรมชาติ
บทพิสูจน์แน่นแค่ไหน
Lean ยืนยันว่าข้อความทางการตามตรรกะจากสัจพจน์ของมัน แต่ไม่สามารถยืนยันได้ว่าข้อความทางการนั้นสื่อสารสิ่งเดียวกับบทความหรือไม่ Anthropic ชี้ว่าไม่มีเครื่องมือใดตรวจสอบการจับคู่นี้ และ OpenAI ระบุว่าไฟล์ Lean ของตนพิสูจน์ขอบเขตที่อ่อนกว่าพาดหัวเล็กน้อย
ตอนนี้ นักวิจัยกลุ่มเดียวกับที่เสนอปัญหา Impagliazzo และ Paturi พร้อมด้วย Ryan Williams จาก MIT กำลังจัดเวิร์กช็อปเพื่อประเมินว่าข้อความทางการนั้นสะท้อน ETH อย่างแท้จริงหรือไม่ จดหมายของพวกเขาเน้นว่าการเข้าร่วมการทบทวนไม่ได้เท่ากับการรับรอง ขณะที่กำลังเขียนบทความนี้ ยังไม่มีใครพบข้อบกพร่องต่อสาธารณะ
Williams กล่าวว่าส่วนหนึ่งของบทพิสูจน์ของ OpenAI ดูเป็นเรื่องปกติ ในขณะที่ "สองหรือสามส่วนที่ดูประหลาด" ยังต้องพิจารณาอย่างเข้มงวด Impagliazzo หนึ่งในผู้เขียน ETH บรรยายผลลัพธ์นี้ว่าน่าประหลาดใจอย่างลึกซึ้ง
อะไรเปลี่ยนและอะไรไม่เปลี่ยน
ในทางปฏิบัติ แทบไม่มีอะไรเปลี่ยนวันนี้ (โล่งอก): อัลกอริทึมใหม่ชนะการลองผิดลองถูกเฉพาะบนอินพุตที่ใหญ่กว่าขนาดที่คอมพิวเตอร์ใด ๆ จะเก็บได้อย่างเทียบไม่ได้
ไม่มีตัวแก้ SAT ที่เร็วขึ้น
บทความของ Anthropic ระบุว่าวิธีการของตนชนะการลองผิดลองถูกเฉพาะบนอินพุตที่ใหญ่แบบมหาศาล สำหรับสูตรทั่วไปที่มีห้าคลอสต่อหนึ่งตัวแปร จุดตัดกันอยู่ที่ตัวเลขที่มีประมาณ 10,000 หลัก ในกรณีทั่วไปที่สุด จะเป็นตัวเลขที่มีราว ๆ 100 ล้านหลัก
ผู้เขียนยังระบุด้วยว่าวิธีของตนไม่น่าจะช่วยอะไรได้กับอินพุตต่ำกว่าประมาณ 10 ล้านตัวแปร ตัวแก้ SAT ที่ใช้ในการตรวจสอบชิป การจัดตารางงาน และการวางแผนจะไม่เร็วขึ้นจากผลลัพธ์นี้
วิทยาการเข้ารหัสไม่พัง
ผลลัพธ์นี้ไม่แตะต้อง P เทียบกับ NP ไม่มีใครอ้างเช่นนั้น OpenAI ระบุว่าได้ตรวจแล้วว่าอัลกอริทึมไม่ทำลายระบบเข้ารหัสจริง และค่อนข้างมั่นใจว่าไม่ทำ
ทฤษฎีต้องเขียนใหม่
ผลกระทบที่ใหญ่กว่าอยู่ที่งานวิจัย ผลลัพธ์ด้านความยากที่สร้างบน ETH หรือ SETH ตอนนี้ต้องหาหลักฐานใหม่ และนักวิจัยบางคนกล่าวว่างานของตนหลายปีอาจต้องทบทวน อย่างไรก็ดี ไม่ได้มีทุกอย่างที่พังลง Anthropic ชี้ว่าผลลัพธ์นี้ไม่ได้หักล้าง ปัญหาเวกเตอร์ตั้งฉาก ซึ่งรองรับผลลัพธ์ด้านความซับซ้อนแบบละเอียดจำนวนมาก
ทำไมจึงสำคัญต่อ AI
พาดหัวข่าวไม่ใช่เรื่อง 3-SAT เท่านั้น แต่คือผู้ที่ค้นพบคำตอบ: สองระบบ AI หักล้างข้อคาดการณ์ที่ผู้เชี่ยวชาญมนุษย์เชื่อถือกันมานานหลายรุ่น โดยอิสระจากกัน
AI ในฐานะผู้ร่วมวิจัย
นักวิจัยบรรยายว่าตอนนี้มีผลลัพธ์ AI ใหม่ ๆ ออกมาทุกสัปดาห์หรือสองสัปดาห์ ทำให้โครงการที่ทำอยู่ถูกรบกวน เครื่องมือเชิงรูปแบบอย่าง Lean กำลังกลายเป็นศูนย์กลาง เพราะช่วยให้มนุษย์ไว้ใจบทพิสูจน์ที่ยาวและเขียนโดยเครื่องได้โดยไม่ต้องอนุมานซ้ำทุกบรรทัด
ทางลัดที่ซ่อนอยู่และการพัฒนาตนเอง
ETH จับความเชื่อที่ว่าบางปัญหาการค้นหาไม่มีทางลัดที่ฉลาด หากความเชื่อนี้ผิด ปัญหาอื่น ๆ ที่ดูยากอย่างชัดเจนอาจซ่อนทางลัดไว้เช่นกัน
กำลังคิดถึงการค้นพบอัลกอริทึมว่าเป็นหนึ่งในพื้นที่ที่ทางลัดดังกล่าวอาจสำคัญมากต่อ การพัฒนาตนเองแบบเวียนเกิด ซึ่งเป็นแนวคิดของระบบ AI ที่ช่วยออกแบบ AI ที่ดีกว่า การใช้งาน AI เพื่อค้นหาอัลกอริทึมที่เร็วขึ้นเป็นหนึ่งในเส้นทางที่เป็นรูปธรรม แม้ว่าไม่มีอะไรในผลลัพธ์นี้จะทำเช่นนั้นได้โดยตรงในวันนี้
หมายความว่าอย่างไรสำหรับผู้ทำงานกับข้อมูล
สำหรับผู้ที่สร้างงานด้วยข้อมูล มีสามบทเรียนที่โดดเด่น:
บทสรุป
หากบทพิสูจน์ผ่านการทบทวนจากผู้เชี่ยวชาญ สมมติฐานเวลาเอ็กซ์โปเนนเชียลจะเข้าร่วมรายการสั้น ๆ ของข้อคาดการณ์ที่เชื่อกันอย่างกว้างขวางแต่กลายเป็นเท็จ (เช่น ข้อคาดการณ์ผลบวกกำลังของออยเลอร์) แต่ P เทียบกับ NP ยังคงเปิดอยู่ และวิทยาการเข้ารหัสยังปลอดภัยในตอนนี้
หมุดหมายถัดไปที่ควรจับตาคือเวิร์กช็อปการทบทวนที่นำโดยผู้เขียนดั้งเดิมของ ETH การนำอัลกอริทึมกลับมาทำซ้ำโดยอิสระ และดูว่ามีใครทำให้ขอบเขตแน่นขึ้นอีกหรือไม่
เพื่อสร้างรากฐานเบื้องหลังเรื่องราวแบบนี้ ลองสำรวจคอร์สของเราเกี่ยวกับโครงสร้างข้อมูลและอัลกอริทึม, การเขียนโปรแกรม Python และการเรียนรู้ของเครื่อง ซึ่งครอบคลุมแนวคิด Big-O ที่ทำให้ผลลัพธ์แบบนี้อ่านเข้าใจได้