โดนัลด์ คนุธ (Donald Knuth) เผยแพร่บทความอธิบายกระบวนการที่ Claude Opus 4.6 ใช้แก้ปัญหาคอมบินาทอริกส์ที่ยังไม่ถูกแก้
(www-cs-faculty.stanford.edu)สรุปประเด็นสำคัญ
- นักวิทยาการคอมพิวเตอร์ โดนัลด์ คนุธ ผู้เขียน 'The Art of Computer Programming (TAOCP)' ประกาศว่าโมเดล AI รุ่นล่าสุด 'Claude Opus 4.6' สามารถแก้ปัญหาคอมบินาทอริกส์ที่ยังไม่ถูกแก้ซึ่งเขาศึกษามาหลายสัปดาห์ได้
- ในปัญหาการหา Hamiltonian cycle decomposition ของกราฟมีทิศทาง Claude ค้นพบโครงสร้างอัลกอริทึมแบบทำให้เป็นกรณีทั่วไปที่ใช้งานได้ ผ่านการรันสคริปต์ Python 31 ครั้งและลูปป้อนกลับของตัวเอง
- คนุธซึ่งในอดีตเคยตั้งข้อสังเกตถึงข้อจำกัดของ generative AI และมีท่าทีสงสัย ได้ประเมินผลลัพธ์ครั้งนี้ว่าเป็น "ความก้าวหน้าอย่างน่าทึ่งของการอนุมานอัตโนมัติและการแก้ปัญหาเชิงสร้างสรรค์" และส่งสัญญาณว่าจะปรับมุมมองเดิมที่มีต่อ AI
การวิเคราะห์เชิงลึก
ปัญหาที่แก้ได้: Hamiltonian Cycle Decomposition
คนุธกำลังศึกษาปัญหาการแยกส่วนในกราฟมีทิศทาง (digraph) บางประเภท ขณะเขียนเล่มถัดไปของ TAOCP ในกราฟที่มีจุดยอด $m^3$ จุดเป็น $ijk$ โดยที่ $0 \le i, j, k < m$ แต่ละจุดยอดมีส่วนโค้ง (arcs) 3 เส้นชี้ไปยัง $i+jk$, $ij+k$, $ijk+$ (โดย $i+ = (i+1) \bmod m$) เป้าหมายคือหาคำตอบทั่วไป (general decomposition) ที่แยกส่วนโค้งเหล่านี้ออกเป็นวงจรมีทิศทางขนาด $m^3$ จำนวน 3 วง สำหรับทุกกรณีที่ $m > 2$ คนุธแก้กรณี $m=3$ ได้แล้ว แต่ยังประสบความยากลำบากในการหาสูตรทำให้เป็นกรณีทั่วไปสำหรับค่าที่มากกว่านั้น
หลักการทำงานและพื้นฐานทางเทคนิค: การให้เหตุผลแบบไฮบริดและลูปการสำรวจอัตโนมัติ
Filip Stappers เพื่อนร่วมงานของคนุธ ได้นำปัญหานี้ป้อนให้กับ 'Claude Opus 4.6' ซึ่งเป็นโมเดลให้เหตุผลแบบไฮบริดรุ่นล่าสุดของ Anthropic โดยไม่ได้ใช้เพียงคำถามธรรมดา แต่กำหนดข้อจำกัดอย่างเข้มงวดในพรอมป์ต์เพื่อบังคับเวิร์กโฟลว์แบบ agentic
Claude ทำการนิยามปัญหาใหม่ในเชิงคณิตศาสตร์ทันที และเขียนสคริปต์ Python (exploreXX.py) เพื่อเริ่มลูปทดสอบสมมติฐาน ตลอดเวลาประมาณ 1 ชั่วโมง มันได้ลองใช้อัลกอริทึมหลากหลายแบบ เช่น brute force, fiber decompositions, simulated annealing และทำการสำรวจทั้งหมด 31 ครั้ง
จุดเปลี่ยนสำคัญของการแก้ปัญหา
โดยเฉพาะในการสำรวจครั้งที่ 25 Claude ได้วิเคราะห์ข้อจำกัดของตัวเองและเปลี่ยนทิศทางการสำรวจ โดยระบุว่า "อัลกอริทึม simulated annealing สามารถหาคำตอบเฉพาะรายได้ แต่ไม่สามารถให้โครงสร้างทางคณิตศาสตร์แบบทั่วไป (general construction) ได้ จึงจำเป็นต้องใช้แนวทางคณิตศาสตร์ล้วน" ในที่สุด ในการสำรวจครั้งที่ 31 มันก็ได้อนุมานโครงสร้างแบบทั่วไปที่ถูกต้องซึ่งทำงานได้เมื่อ $m$ เป็นจำนวนคี่ จากรูปแบบเชิงโครงสร้างของการสำรวจก่อนหน้า คนุธได้ต่อยอดจากผลลัพธ์นี้เพื่อทำบทพิสูจน์ทางคณิตศาสตร์ให้เสร็จสมบูรณ์ และตั้งชื่อมันว่า 'Claude-like decompositions'
โค้ดและข้อมูลสำคัญ
ต่อไปนี้คือข้อจำกัดหลัก (พรอมป์ต์) ที่ Filip Stappers มอบให้ Claude และบางส่วนของบันทึกการประเมินตนเองที่ Claude เขียนไว้
# 1. ข้อจำกัดของเวิร์กโฟลว์ที่มอบให้ Claude (บังคับควบคุมลูปและการจัดทำเอกสาร)
"""
After EVERY exploreXX.py run, IMMEDIATELY update this file [plan.md] before doing anything else.
No exceptions. Do not start the next exploration until the previous one is documented here.
"""
# 2. การนิยามปัญหาใหม่ทางคณิตศาสตร์ของ Claude (แนวทางเริ่มต้น)
"""
Need sigma: Z3 m — S3, assigning a permutation of {0,1,2} at each vertex;
cycle c at vertex v goes in direction sigma(v)[c].
Each resulting functional digraph must be a single Hamiltonian cycle.
"""
# 3. การประเมินตนเองของ Claude หลังการสำรวจครั้งที่ 25 (การเปลี่ยนทิศทาง)
"""
SA(Simulated Annealing) can find solutions but cannot give a general construction.
Need pure math.
"""
10 ความคิดเห็น
คนที่อยู่ในตำราเรียนยังคงเพิ่มอะไรเข้าไปในตำราเรียนอยู่เรื่อยเลยนะ....
(เห็นด้วย)
ก็แน่อยู่แล้ว บทบาทของท่านผู้นั้นก็คือการเขียนตำราอยู่แล้วนี่นา (พยักหน้า)
ฮ่าๆๆๆ ต่อไปคงจะเพิ่มอะไรด้วย AI ได้อีกเพียบเลยนะครับ
แปลว่า TAOCP ยังออกต่ออยู่นี่เอง
เขาแชร์วิธีใช้ AI เพื่อแก้โจทย์คณิตศาสตร์แบบตรงไปตรงมา แล้วก็เขียนบทความวิชาการด้วย TeX ที่ตัวเองสร้างขึ้นเอง.... เท่มาก
เพราะบทความนี้ทำให้ผมเพิ่งรู้จัก TAOCP เป็นครั้งแรก คงต้องลองค่อย ๆ อ่านดูสักหน่อยครับ
ถึงกับเขียนเล่มถัดไปของ TAOCP เลยเหรอ
แบบนี้สงสัยว่าซีรีส์นี้น่าจะมีเล่มต่อออกมาอีกนะเนี่ย 55555
เขายังมีชีวิตอยู่อีกเหรอ?
ตอนนี้ก็ยังคงแก้ไขอยู่...