Donald Knuth công bố bài báo về quá trình Claude Opus 4.6 giải một bài toán tổ hợp chưa có lời giải
(www-cs-faculty.stanford.edu)Tóm tắt chính
- Donald Knuth, nhà khoa học máy tính và tác giả của 'The Art of Computer Programming (TAOCP)', cho biết mô hình AI mới nhất 'Claude Opus 4.6' đã giải được một bài toán tổ hợp chưa có lời giải mà ông đã nghiên cứu suốt nhiều tuần.
- Trong bài toán tìm phép phân rã chu trình Hamilton trên đồ thị có hướng, Claude đã phát hiện ra một cấu trúc thuật toán tổng quát có thể hoạt động thông qua 31 lần chạy script Python và vòng lặp tự phản hồi.
- Knuth, người trước đây từng hoài nghi và chỉ ra các giới hạn của AI tạo sinh, đánh giá kết quả lần này là “một bước tiến đầy kịch tính trong suy diễn tự động và giải quyết vấn đề sáng tạo”, đồng thời cho thấy ông sẽ điều chỉnh quan điểm trước đây về AI.
Phân tích chuyên sâu
Bài toán được giải: phân rã chu trình Hamilton (Hamiltonian Cycle Decomposition)
Knuth đang nghiên cứu một bài toán phân rã trên một số đồ thị có hướng (digraph) cụ thể trong quá trình viết tập tiếp theo của TAOCP. Trong đồ thị có $m^3$ đỉnh gồm các đỉnh $ijk$ với $0 \le i, j, k < m$, mỗi đỉnh có 3 cung (arcs) đi tới $i+jk$, $ij+k$, $ijk+$ (trong đó $i+ = (i+1) \bmod m$). Mục tiêu là tìm một lời giải tổng quát (general decomposition) để phân rã các cung này thành 3 chu trình có hướng độ dài $m^3$ cho mọi trường hợp $m > 2$. Knuth đã giải được trường hợp $m=3$, nhưng gặp khó khăn trong việc rút ra công thức tổng quát cho các giá trị lớn hơn.
Nguyên lý triển khai và nền tảng kỹ thuật: suy luận lai và vòng lặp khám phá tự chủ
Đồng nghiệp của Knuth là Filip Stappers đã đưa bài toán này vào 'Claude Opus 4.6', mô hình suy luận lai mới nhất của Anthropic. Khi đó, ngoài việc đặt câu hỏi đơn thuần, ông còn đưa vào prompt các ràng buộc mạnh nhằm buộc mô hình phải vận hành theo workflow mang tính tác tử (agentic).
Claude ngay lập tức tái định nghĩa bài toán về mặt toán học và viết script Python (exploreXX.py) để bắt đầu vòng lặp kiểm chứng giả thuyết. Trong khoảng 1 giờ, mô hình đã thử nhiều thuật toán khác nhau như brute force, phân rã fiber (fiber decompositions), simulated annealing, và thực hiện 31 lượt khám phá.
Bước ngoặt then chốt trong quá trình giải bài toán
Đặc biệt, ở lần khám phá thứ 25, Claude tự phân tích giới hạn của chính mình và chuyển hướng tìm kiếm, nói rằng “thuật toán simulated annealing có thể tìm ra lời giải riêng lẻ nhưng không thể đưa ra cấu trúc toán học tổng quát (general construction), vì vậy cần một cách tiếp cận toán học thuần túy”. Cuối cùng, ở lần khám phá thứ 31, dựa trên các mẫu cấu trúc từ những lần thử trước, Claude đã suy ra được cấu trúc tổng quát chính xác hoạt động khi $m$ là số lẻ. Dựa trên kết quả này, Knuth đã hoàn tất chứng minh toán học và đặt tên cho nó là 'phân rã kiểu Claude (Claude-like decompositions)'.
Mã và dữ liệu chính
Dưới đây là các ràng buộc cốt lõi trong prompt mà Filip Stappers đưa cho Claude, cùng một phần log tự đánh giá do Claude ghi lại.
# 1. Ràng buộc workflow áp cho Claude (kiểm soát vòng lặp và bắt buộc tài liệu hóa)
"""
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 tái định nghĩa bài toán toán học (cách tiếp cận ban đầu)
"""
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. Tự đánh giá của Claude sau lần khám phá thứ 25 (chuyển hướng tiếp cận)
"""
SA(Simulated Annealing) can find solutions but cannot give a general construction.
Need pure math.
"""
9 bình luận
Người xuất hiện trong sách giáo khoa lại cứ liên tục bổ sung thêm nội dung vào chính sách giáo khoa....
(Đồng ý)
Thì viết giáo trình vốn là vai trò của ngài ấy mà (gật gù)
kkkkkk giờ có lẽ ông ấy sẽ còn bổ sung thêm nữa bằng AI đấy nhỉ
Thì ra TAOCP vẫn còn ra tiếp à
Ông đã chia sẻ nguyên cách dùng AI để giải bài toán, rồi còn viết bài báo bằng chính TeX do mình tạo ra.... Quá ngầu luôn
Nhờ bài viết này mà tôi mới biết đến TAOCP, chắc phải từ từ đọc thử mới được.
Ông ấy vẫn còn sống à?
Ngài vẫn đang đính chính...