Các chu trình của Claude [PDF]

 (www-cs-faculty.stanford.edu)
4 điểm bởi GN⁺ 2026-03-04 | 1 bình luận | Chia sẻ qua WhatsApp
  • Mô hình Claude Opus 4.6 của Anthropic đã giải được bài toán phân rã chu trình Hamilton có hướng mà Donald Knuth đã nghiên cứu trong vài tuần
  • Bài toán là tìm phân rã thành ba chu trình Hamilton của một đồ thị có hướng với (m^3) đỉnh, và Claude đã giải hoàn chỉnh bài toán này cho m lẻ (odd m)
  • Claude lần lượt thực hiện nhiều chiến lược tìm kiếm khác nhau như phân rã “fiber”, mẫu “serpentine” 3D, tìm kiếm theo chiều sâu (DFS), simulated annealing
  • Cuối cùng, Claude suy ra được một lời giải tổng quát dưới dạng chương trình Python, và Filip Stappers đã kiểm chứng với mọi m lẻ từ 3 đến 101 để xác nhận phân rã hoàn chỉnh
  • Knuth đánh giá kết quả này là một bước tiến đột phá trong suy luận tự động và giải quyết vấn đề sáng tạo, đồng thời nêu rõ rằng trường hợp m chẵn vẫn chưa được giải quyết

Bối cảnh và định nghĩa của bài toán

  • Chủ đề nghiên cứu liên quan đến chu trình Hamilton có hướng (directed Hamiltonian cycles), dự kiến sẽ được đưa vào một tập sắp tới của The Art of Computer Programming
  • Đồ thị gồm (m^3) đỉnh (ijk), và từ mỗi đỉnh có ba cạnh: (i+jk), (ij+k), (ijk+)
  • Mục tiêu là tìm một lời giải tổng quát để phân rã các cạnh này thành ba chu trình có hướng độ dài (m^3) với mọi (m>2)

Quá trình khám phá của Claude

  • Claude Opus 4.6 là mô hình hybrid reasoning của Anthropic; Filip Stappers đã đưa ra bài toán và yêu cầu ghi lại quá trình tiến triển
  • Ở giai đoạn đầu, Claude tái diễn giải bài toán thành đồ thị hàm và bài toán gán hoán vị, rồi thử các cách tiếp cận tuyến tính và hàm bậc hai nhưng đều thất bại
  • Sau đó, Claude lần lượt thử nghiệm tìm kiếm DFS, phân tích mẫu serpentine 2D, mẫu dựa trên mã Gray 3D
  • Tiếp theo, Claude đưa vào cách tiếp cận phân rã fiber, phân tích cấu trúc phân tầng theo (s = (i+j+k) \mod m), rồi tìm được lời giải cục bộ nhờ simulated annealing (SA)

Khám phá lời giải và kiểm chứng

  • Ở bước khám phá thứ 31, Claude tạo ra một chương trình Python dùng quy tắc phụ thuộc một tọa độ duy nhất theo từng fiber
  • Chương trình này tạo được ba chu trình Hamilton hoàn chỉnh với m=3,5,7,9,11
  • Filip Stappers đã kiểm thử nó với mọi m lẻ từ 3 đến 101 và xác nhận phân rã hoàn chỉnh
  • Knuth sau đó đơn giản hóa lời giải thành mã C và chứng minh về mặt toán học rằng mỗi chu trình thực sự có độ dài (m^3)

Khái quát hóa và phân tích toán học

  • Xác nhận rằng một số chu trình Hamilton ở m=3 có thể khái quát cho mọi m lẻ
    • Với (m=3), trong 11.502 chu trình có 1.012 chu trình khái quát được sang (m=5), và 996 chu trình còn khái quát được đến (m=7)
    • 996 chu trình này có thể khái quát cho mọi m lẻ > 1
  • Phân rã “Claude-like” được định nghĩa bằng các quy tắc đơn giản chỉ phụ thuộc vào giá trị biên của i, j, s (0 hoặc m−1)
  • Định lý: để một phân rã “Claude-like” đúng với mọi m lẻ > 1, thì ba chu trình ở m=3 phải là các chu trình Hamilton có thể khái quát hóa
  • Kết quả tính toán cho thấy có 760 phân rã Claude-like đúng với mọi m lẻ

Tính chưa được giải của m chẵn và kết luận

  • Trường hợp m chẵn vẫn ở trạng thái chưa được giải (open)
    • (m=2) đã được nghiên cứu trước đây chứng minh là bất khả thi
    • Claude đã tìm được lời giải cục bộ với (m=4,6,8) nhưng không thể khái quát hóa
  • Trong quá trình tìm kiếm cho m chẵn, Claude xuất hiện lỗi và hành vi bất thường nên việc khám phá bị dừng lại
  • Knuth đánh giá đây là một thành tựu mang tính lịch sử của suy luận tự động dựa trên AI, và nói rằng đó là một bước tiến xứng đáng với cái tên Claude Shannon

Phụ lục: quy tắc của hai chu trình còn lại

  • Chu trình thứ hai (c=1):
    • Nếu (s=0) thì tăng j, nếu (0<s<m−1) thì tăng i, nếu (s=m−1) thì khi i>0 tăng k, còn i=0 thì tăng j
  • Chu trình thứ ba (c=2):
    • Khi (s=0), nếu j<m−1 thì tăng i, còn j=m−1 thì tăng k
    • Khi (0<s<m−1), nếu i<m−1 thì tăng k, còn i=m−1 thì tăng j
    • Khi (s=m−1) thì tăng i
  • Thứ tự các đỉnh của từng chu trình tại s=0 được nêu rõ, từ đó có thể chứng minh cấu trúc của toàn bộ chu trình

Bài viết liên quan

1 bình luận

 
GN⁺ 2026-03-04
Ý kiến trên Hacker News

  • Thật thú vị khi nghĩ về những miền bài toán mà khả năng mở rộng của RL có thể áp dụng được
    Trước đây phải phụ thuộc vào nhận thức của con người, nhưng giờ những mẫu như vậy đã được hòa vào phân phối xác suất, nên ai cũng có thể tiếp cận
    Tuy vậy, khi ranh giới của khoa học tiếp tục mở rộng, vẫn chưa rõ liệu mô hình có theo kịp được hay không
    Đến năm 2030, để Anthropic giữ Claude luôn cập nhật, có lẽ sẽ cần (a) học liên tục cho một mô hình cố định hoặc (b) huấn luyện liên tục, mà cả hai đều không dễ

    • Các mô hình open-weight giống như một viên nang thời gian
      Sau thời điểm knowledge cutoff, chúng sẽ mãi bị giữ lại ở chính thời điểm đó
    • Nếu việc chia sẻ dữ liệu được cho phép, thì kết quả suy luận hôm nay có thể trở thành dữ liệu huấn luyện của ngày mai
      Cũng có thể hình dung một mô hình cung cấp suy luận miễn phí cho các nhà nghiên cứu, đổi lại dùng chính quá trình suy nghĩ (trace) đó làm dữ liệu huấn luyện
    • Nghe những gì các nhà nghiên cứu gần đây nói, có vẻ kiến trúc mô hình tương lai sẽ phát triển theo hướng mở rộng mạnh context window
      Các mô hình như Qwen3-next, Qwen3.5, Nemotron 3 Nano hỗ trợ cửa sổ hàng triệu token trong khi giảm chi phí bộ nhớ bằng hybrid attention
    • Phần lớn nghiên cứu và học tập hiện đã diễn ra thông qua LLM và coding agent
      Vòng phản hồi thời gian thực thông qua xác minh của con người, chạy mã và tìm kiếm đang đóng vai trò là tín hiệu huấn luyện cho mô hình
    • Biết đâu đến năm 2030, chính Claude sẽ là bên giữ cho Anthropic luôn cập nhật
      Nói nửa đùa thôi, nhưng cũng không hoàn toàn là chuyện bất khả thi

  • Điều này gợi nhớ đến cuộc trò chuyện giữa Wolfram và Knuth về GPT-4 trước đây
    Khi đó Knuth còn hoài nghi, nhưng dường như sau khi thấy những mô hình như Opus 4.6 gần đây, ông đã dịu lại phần nào
    Việc thay đổi suy nghĩ theo bằng chứng mới là một điều rất đáng quý
    Có thể xem cuộc trò chuyện liên quan tại đây

    • Cập nhật xác suất tiên nghiệm (prior) theo bằng chứng mới chính là sức hấp dẫn của thống kê Bayes
      Đó cũng là cốt lõi của tư duy khoa học

  • Tôi thấy phần mở đầu bài viết của Knuth có phần dễ gây hiểu nhầm
    Nó khiến người ta có cảm giác như Claude đã trực tiếp giải bài toán, nhưng thực tế là Claude tạo ra các ví dụ còn Knuth khái quát hóa chúng thành chứng minh

    • Tôi cũng đã thử những thí nghiệm tương tự với Claude, và sự cộng hưởng giữa con người với LLM thật sự rất lớn
      LLM không giỏi định hướng ban đầu, nhưng một khi đã có hướng đi thì lại đào sâu khám phá rất tốt
      Nếu để một mình nó sẽ đi chệch hướng, nhưng khi có con người dẫn dắt thì nó trở thành một đối tác tuyệt vời
    • Tôi không nghĩ Knuth đã đánh giá quá cao
      Claude đã đóng vai trò đâm thẳng vào cốt lõi của bài toán, còn con người chỉ là người gọt giũa lại
    • Cũng có thể xem Claude là bên đã thực hiện phần ‘giải quyết’ mà Knuth nói đến
      Việc chỉnh lý chứng minh chỉ là công việc thứ yếu
    • Khả năng quay lại những lần thử trước để tự phản tỉnh và sửa đổi rõ ràng trông giống một dấu hiệu của trí tuệ

  • Phần Claude dừng lại ở trường hợp chẵn khá thú vị
    Có lẽ họ đã dùng claude.ai hoặc claude code, và nó dường như đã rơi vào trạng thái quá tải ngữ cảnh (dumb zone)

    • Sẽ rất hay nếu có thể trực quan hóa dumb zone này
      Chẳng hạn hiển thị biểu đồ mức sử dụng ngữ cảnh như Copilot, để người dùng có thể nhận biết, thì sẽ khá hữu ích
    • Cuối cùng thì nếu không nén ngữ cảnh (compacting), kết quả sẽ trở nên rất lộn xộn
    • Việc nhắc đến ‘plan document’ cho thấy có vẻ họ đã dùng tài liệu quản lý phiên làm việc
    • Cũng có người thắc mắc dumb zone thực chất là gì

  • Có người đã thử cho Claude giải bài toán ghép pentomino do Arthur C. Clarke làm nổi tiếng
    Khi biểu diễn bàn cờ và các mảnh bằng số nguyên 64-bit, Claude đã tạo được chương trình C# giải rất nhanh, nhưng ở trường hợp 20x3 lại cho ra đáp án sai vì ánh xạ sai
    Khá thú vị vì đây là kiểu sai lầm mà con người cũng có thể mắc phải

  • Tóm lại, Knuth đưa ra bài toán và một người bạn đã dùng Claude thực hiện hơn 30 lượt tìm kiếm
    Claude tạo một chương trình Python giải được trường hợp lẻ, còn Knuth chứng minh cách tiếp cận đó
    Trường hợp chẵn vẫn là một bài toán chưa được giải quyết

    • Nhưng cụm “careful human guidance” mà Knuth dùng có vẻ hơi cường điệu
      Thực tế dường như chỉ là thỉnh thoảng con người nhắc lại khi Claude thường xuyên bị khựng hoặc mắc lỗi
    • Điều Knuth muốn nhấn mạnh dường như là chứng minh hình thức vẫn là phần việc của con người
      Còn ý tưởng cốt lõi thực sự đến từ ai thì vẫn chưa rõ

  • Dạo này đúng là thời điểm rất thú vị để làm việc với những bài toán chưa có lời giải
    Tôi cũng muốn quay lại nghiên cứu từ 10 năm trước và cùng Claude khám phá lại chúng

  • Có vẻ điểm mạnh của LLM nằm ở ba thứ: lượng tri thức khổng lồ, khả năng kết nối, và thử sai không biết mệt
    Khi ba yếu tố này kết hợp lại, đôi khi sẽ tạo ra kết quả đáng kinh ngạc
    Biết đâu chứng minh P≠NP cũng nằm ở một mối liên hệ mờ nhạt mà con người chưa từng nhìn ra

    • Mục cuối thực ra có thể không hẳn là đặc tính của riêng LLM mà là của agent loop
      LLM chỉ là một thành phần trong đó thôi
    • Dù vậy, khả năng lặp lại việc khám phá mà không biết mệt vẫn là lợi thế rất lớn so với con người
      Nếu các điều kiện khác ngang nhau, đây có thể là khác biệt mang tính quyết định
    • Tôi hoàn toàn đồng ý với ý rằng kết hợp cả ba thứ sẽ tạo ra những kết quả tuyệt vời
    • Nhưng cũng thấy đáng sợ khi năng lực như vậy có thể được dùng trong hệ thống giám sát
    • ‘Khả năng kết nối’ thực ra có vẻ chỉ giới hạn ở những liên kết đã tồn tại trong dữ liệu huấn luyện
      Việc tạo ra các kết nối hoàn toàn mới vẫn còn khó

  • Tôi nghi ngờ việc nói “LLM chỉ là cỗ máy dự đoán từ tiếp theo” có thật sự đúng không
    Nếu vậy thì phải giải thích kiểu giải bài toán này thế nào? Có phải đó là ‘suy nghĩ’ không?

    • Nếu có thể dự đoán hoàn hảo từ mà Einstein sẽ nói tiếp theo, thì như vậy đã là hiện thực hóa trí tuệ rồi
      Cách diễn đạt “từ có xác suất cao nhất” là một lối giải thích quá đơn giản hóa
    • Mô tả đó đúng với base model, nhưng các mô hình như Opus 4.6 còn có RLHF và huấn luyện bổ sung chồng lên trên
      Cuối cùng thì “khả năng dự đoán tốt điều sẽ xảy ra tiếp theo” bản thân nó cũng có thể là định nghĩa của trí tuệ
    • Base model học các mẫu “Answer:” trên web nên một cách tự nhiên cũng học được mẫu giải quyết vấn đề
      Nhờ RLHF, nó được thưởng không phải cho việc dự đoán đơn thuần mà cho việc đưa ra câu trả lời hữu ích
      Vì thế những từ như “delve” xuất hiện với tần suất quá cao
      Xem thêm tài liệu AI SIGNS
    • Xét cho cùng thì nó vẫn là việc rút ra từ từ một phân phối xác suất, nhưng chính bản thân phân phối đó mới là cốt lõi của trí tuệ
      LLM đang học phân phối đó
    • Cơ chế đơn giản kiểu “từ có xác suất cao nhất” khi kết hợp với toàn bộ tri thức của nhân loại sẽ có sức mạnh khổng lồ
      Đem nó ra đơn giản hóa rồi mỉa mai là một cách nhìn bỏ lỡ bản chất của công nghệ

  • Thú vị thật, đây lại là báo cáo của chính Knuth
    Đã đến lúc đọc và hiểu trực tiếp mà không cần nhờ LLM