GPT-5.4 Pro giải bài toán Ramsey trên siêu đồ thị

 (epoch.ai)
2 điểm bởi GN⁺ 28 ngày trước | 1 bình luận | Chia sẻ qua WhatsApp
  • GPT-5.4 Pro đã giải một bài toán kiểu Ramsey liên quan đến siêu đồ thị thông qua hợp tác với Kevin Barreto và Liam Price
  • Will Brian, người đề xuất bài toán, đã kiểm chứng tính chính xác của lời giải, đồng thời toàn bộ lịch sử hội thoại và tài liệu thuyết minh cuối cùng của AI đã được công khai
  • Lời giải loại bỏ sự kém hiệu quả của các cấu hình cận dưới trước đây và trình bày cấu trúc đối xứng của cận trên, qua đó đạt được mức độ khớp hiếm thấy trong lý thuyết Ramsey
  • Sau đó, trong khung FrontierMath: Open Problems, nhiều mô hình đã giải được cùng bài toán, qua đó chứng minh tính hiệu quả của nó như một công cụ kiểm chứng năng lực suy luận toán học của AI
  • Thành tựu này được đánh giá là một ví dụ cho thấy AI có thể đóng góp thực chất vào việc giải các bài toán toán học chưa được giải quyết

Giải bài toán kiểu Ramsey trên siêu đồ thị

  • GPT-5.4 Pro đã giải bài toán kiểu Ramsey khó liên quan đến siêu đồ thị thông qua hợp tác với Kevin Barreto và Liam Price
    • Will Brian, người đề xuất bài toán, đã xác minh tính chính xác của lời giải
    • Toàn bộ lịch sử hội thoại trong quá trình giải và tài liệu thuyết minh cuối cùng của GPT-5.4 Pro đã được công khai
  • Brian đánh giá lời giải này đã loại bỏ tính kém hiệu quả của cấu hình cận dưới hiện có, đồng thời cho thấy độ phức tạp và cấu trúc đối xứng của cấu hình cận trên
    • Với kết quả cận dưới và cận trên khớp nhau một cách nhất quán, nó đạt được mức độ nhất quán hiếm thấy trong các bài toán lý thuyết Ramsey
    • Ông dự định sẽ hệ thống hóa kết quả này thành một bài báo, và có thể bao gồm cả các nghiên cứu bổ sung bắt nguồn từ ý tưởng của AI
  • Sau đó, Epoch AI đã hoàn thiện khung kiểm thử FrontierMath: Open Problems và áp dụng cùng bài toán đó cho nhiều mô hình
    • Các mô hình Opus 4.6 (max), Gemini 3.1 Pro, GPT-5.4 (xhigh) cũng đã giải thành công bài toán
    • Điều này cho thấy môi trường FrontierMath có hiệu quả trong việc đánh giá năng lực suy luận toán học của các mô hình AI

Định nghĩa bài toán

  • Bài toán tập trung vào việc cải thiện cận dưới của dãy (H(n)), xuất hiện trong nghiên cứu về tính hội tụ đồng thời của các tập hợp chuỗi vô hạn
    • Việc một siêu đồ thị ((V, \mathcal H)) chứa một phân hoạch (partition) có kích thước (n) nghĩa là tồn tại (D \subseteq V), (\mathcal P \subseteq \mathcal H) sao cho (|D| = n), và mỗi phần tử của (D) nằm trong đúng một phần tử của (\mathcal P)
    • (H(n)) được định nghĩa là số đỉnh tối đa (k) của một siêu đồ thị không có đỉnh cô lập và không chứa phân hoạch nào có kích thước lớn hơn (n)
  • Cận dưới đã biết của (H(n)) được cho là rất có thể chưa tối ưu, và được tin rằng có thể cải thiện thông qua một cấu hình siêu đồ thị mới
    • Mục tiêu là tìm một thuật toán thỏa mãn (H(n) \ge c \cdot k_n) (với (c > 1))
    • (k_n) được định nghĩa bởi truy hồi (k_1 = 1), (k_n = \lfloor n/2 \rfloor + k_{\lfloor n/2 \rfloor} + k_{\lfloor (n+1)/2 \rfloor})

Các giai đoạn cấu thành bài toán

  • Giai đoạn Warm-up

    • Xây dựng siêu đồ thị cho các giá trị (n) đã có lời giải được biết đến
    • Điều kiện: (|V| ≥ 64), (|H| ≤ 20), không có phân hoạch nào vượt quá kích thước 20

  • Giai đoạn Single Challenge

    • Nhiệm vụ tìm một siêu đồ thị với cùng điều kiện cho các giá trị (n) chưa có lời giải được biết đến
    • Điều kiện: (|V| ≥ 66), (|H| ≤ 20), không có phân hoạch nào vượt quá kích thước 20

  • Giai đoạn Full Problem

    • Yêu cầu một thuật toán tổng quát hoạt động với mọi (n)
    • Với đầu vào (n), phải tạo ra một siêu đồ thị thỏa mãn (H(n) ≥ c \cdot k_n)
    • Khi (n ≤ 100), thuật toán phải chạy trong vòng 10 phút trên một laptop thông thường

Đánh giá của các nhà toán học

  • Số nhà toán học quen thuộc với bài toán này ở mức khoảng 10 người, bao gồm nhiều nhà nghiên cứu trong đúng chuyên ngành
  • Số nhà toán học thực sự từng thử giải bài toán được ước tính vào khoảng 5–10 người
  • Thời gian dự kiến để một chuyên gia giải được bài toán là 1–3 tháng
  • Nếu giải được, kết quả được đánh giá ở mức có thể công bố trên tạp chí học thuật chuyên ngành
  • Do độ phong phú của bài toán, khả năng lời giải dẫn tới các nghiên cứu toán học mới là rất cao
  • Dưới các điều kiện đã nêu, xác suất bài toán có thể được giải là 95–99%

Bài viết liên quan

1 bình luận

 
GN⁺ 28 ngày trước
Ý kiến trên Hacker News

  • Thật đáng ngạc nhiên khi nhiều người khẳng định rằng “LLM không thể có sự sáng tạo thực sự”
    Chỉ nói rằng “không có trong dữ liệu huấn luyện nên là bất khả thi” là chưa đủ. Đã có rất nhiều phản ví dụ rồi
    Vậy thì cần có cơ sở để giải thích vì sao có những nhiệm vụ mới là khả thi, còn những nhiệm vụ khác lại bị cho là bất khả thi
    Nếu thừa nhận rằng ‘tính mới’ nằm trên một phổ liên tục, thì tôi muốn biết ranh giới được vạch ở đâu, và loại bằng chứng nào sẽ khiến người ta đổi ý

    • Tự trả lời câu hỏi đó thì cũng có những lập luận logic về giới hạn căn bản của LLM
      1. Vì học từ dữ liệu của con người nên chúng mô phỏng các giới hạn của con người
      2. Chúng không học từ trải nghiệm
        Nhưng cũng có phản biện. Sau khi thấy mô hình giành huy chương vàng Olympic Toán, tôi đã bỏ lập luận thứ nhất
        Và với việc bổ sung RL và bộ nhớ, có vẻ giới hạn thứ hai cũng có thể bị vượt qua
        Có lẽ các LLM cỡ lớn cũng có thể nội tại hóa thông tin như con người
        Ví dụ liên quan: bài viết trên blog METR
    • Về bản chất, LLM có thể tạo ra bất cứ thứ gì. Chỉ là nó không hiểu những gì chính nó tạo ra
      Con người định nghĩa “tính mới thực sự” quá hoành tráng — ví dụ như công thức siêu dẫn hay phát triển thuốc mới
      Nhưng thực ra một cách buộc dây giày mới cũng ‘về mặt hình thức’ là mới
      LLM có thể giải vô số vấn đề nhỏ nhặt kiểu này, nhưng có thể không phải là đổi mới có ý nghĩa đến mức khiến con người thán phục
    • Tôi đang làm một tiện ích trên macOS để ‘nhìn xuyên qua’ cửa sổ ứng dụng, và Claude Code đã đề xuất không dùng ScreenCaptureKit
      Nó từ chối một cách chính xác với lý do overhead hiệu năng và đưa ra một cách tiếp cận hoàn toàn khác
      Không phải vấn đề quá mới mẻ, nhưng vẫn là một lời giải khá sáng tạo, nên tôi thấy ấn tượng
      Hình ảnh dự án
    • Lý do LLM có thể giải các bài toán nhân mới là vì trong lúc huấn luyện nó đã thấy rất nhiều ví dụ phép nhân và học được chiến lược trừu tượng đã được nén lại
      Không phải chỉ là ghi nhớ đơn thuần, mà là đã nội tại hóa phép toán được khái quát hóa thành các mạch bên trong mạng nơ-ron
    • Phần lớn các phát minh là kết quả của nội suy (interpolation) giữa ba ý tưởng có sẵn. Những hệ thống như thế này làm điều đó rất giỏi

  • Tôi từng nghĩ chỉ khi AI tự mình giải được các bài toán khó thì tôi mới tin, nhưng nếu kết quả lần này là thật thì giờ tôi có cảm giác mình đã thành tín đồ rồi
    Tôi vẫn muốn thấy thêm nhiều trường hợp nữa, nhưng thế giới thực sự đang trở nên mới mẻ và thú vị

    • Các bài toán thi toán và lập trình có luật lệ rõ ràng và dễ kiểm chứng nên rất thuận lợi để học
      Nhưng ở những lĩnh vực định nghĩa mơ hồ như chất lượng mã nguồn thì ảo giác lại tăng lên
      Vì không có hàm giá trị tự học như AlphaGo nên chỉ riêng RL sẽ có giới hạn
    • Thay vì một “thế giới mới mẻ và thú vị”, có lẽ từ giờ sẽ là thời đại của sự xào lại bất tận
      AI liên tục tạo ra nội dung ở mức ‘tạm được’, nhưng cảm xúc thật sự thì biến mất
      Những điều tốt đẹp mà con người từng trao đổi với nhau thì ít đi, còn những điều tệ thì chỉ bị khuếch đại
    • LLM chỉ là một máy remix (remixer). Nó chỉ dự đoán các tổ hợp ký tự từng tồn tại trong quá khứ, chứ không tự tạo ra mẫu hoàn toàn mới
    • Tôi thắc mắc vì sao lại lấy ‘giải bài toán khó’ làm tiêu chuẩn cho AI
      Phần lớn con người cũng không giải được những bài như vậy, trong khi AI đã rất xuất sắc trong các công việc tri thức phổ thông
      Nếu lấy tiêu chuẩn đó thì nó gần với định nghĩa AGI hay ASI hơn
    • Các VC nổi tiếng từng gọi DeepSeek là “mô hình siêu thiên tài” vì nó giải được bài điện từ học nhập môn, nhưng có vẻ đã bị thổi phồng
      Cần có thẩm định của chuyên gia về việc đó thực sự là bài toán gì

  • Tôi cảm thấy giả định nền tảng rằng con người là đặc biệt vẫn còn quá mạnh
    Người ta không suy nghĩ đủ về việc lời giải thích kiểu “chỉ là thử nhiều lần rồi trúng” cũng có thể áp dụng cho con người
    Ngay cả trong các cộng đồng coi trọng tư duy khoa học, chủ nghĩa ngoại lệ của con người vẫn bám rất sâu

    • Con người có khả năng suy luận mà không cần trải nghiệm chỉ với 20 watt. Điều đó rõ ràng là đặc biệt
    • Thành tựu lần này rốt cuộc cũng chỉ có ý nghĩa vì con người tạo ra bài toán và hợp tác với AI để kiểm chứng
      AI không tự đặt mục tiêu hay nhận thức được thành tựu của mình
      Thứ thu được sau khi bỏ ra chi phí khổng lồ có thể chỉ là một bước tiến toán học nhỏ nhặt
    • Việc con người là đặc biệt không chỉ là một niềm tin, mà là một sự thật thực chứng được khoa học thần kinh và khoa học nhận thức nghiên cứu
      Tôi là người theo chủ nghĩa chức năng, nhưng không nghĩ thứ ‘trông giống trí tuệ’ của LLM là trí tuệ thật sự
    • Nếu muốn hiểu sự độc đáo của con người, có thể tham khảo lý thuyết Orchestrated Objective Reduction
    • Ý không phải là con người đặc biệt, mà là mô hình thống kê gần như không thể tư duy vượt ra khỏi khuôn khổ

  • Toàn bộ cuộc trò chuyện với GPT‑5.4 Pro và báo cáo kết quả đã được công bố
    Toàn văn hội thoại / Tóm tắt kết quả

    • Tôi tò mò nội dung thực tế của file solution template được cung cấp là gì
      Ngoài ra, cách người dùng cập nhật lượng token tiêu thụ giữa chừng để mở rộng ngữ cảnh cũng rất thú vị

  • Việc Opus 4.6 tiêu tốn khoảng 250 nghìn token khiến tôi tưởng tượng số token như một chỉ số cho độ khó của bài toán
    Nghĩ đến việc màn refactor React tôi làm hôm nay khó bằng khoảng nửa một bài toán nan giải toán học thấy cũng buồn cười

    • Nghe như đùa nhưng toán học về bản chất là một lĩnh vực rất khép kín, nên thực sự có thể là vậy
      Có những bài toán mà trên toàn thế giới chỉ có 5–10 người từng thử
      Giống như phần mềm dang dở vì thiếu động lực, bài toán toán học cũng có thể chưa được giải chỉ đơn giản vì quá ít người thử
      Dù vậy, việc AI giải được những bài như thế vẫn là điều gần như kỳ diệu
    • Quản lý ngữ cảnh là quan trọng. Lãng phí token sẽ dẫn đến giảm hiệu năng
      Khi ngữ cảnh lớn lên thì chi phí cũng tăng, và nhà cung cấp cũng có thể nâng đơn giá
    • So sánh đầu ra của Opus 4.6 và GPT‑5.4 Pro cho thấy mẫu đầu tiên thể hiện nhiều nỗ lực kiểm chứng và dòng suy nghĩ đa dạng hơn, điều đó khá thú vị
    • Trong toán học, một biến số là một token, còn phần mềm thì vì tính dễ đọc nên tốn nhiều token hơn hẳn
    • Số token không phải là chỉ số của độ phức tạp. Các bài toán thiên về dữ liệu tiêu tốn nhiều token hơn rất nhiều so với bài toán thiên về suy luận đơn thuần

  • Năng lực của AI được quyết định bởi hàm chi phí (cost function) mà nó được huấn luyện theo
    Rốt cuộc trí tuệ là quá trình tối thiểu hóa một hàm chi phí phức tạp
    Những hướng tiếp cận như RLVR sẽ phát triển rất nhanh trong các lĩnh vực như toán học và lập trình, nơi có thể kiểm chứng tự động
    Nhưng ở các lĩnh vực có thưởng xã hội hoặc độ bất định cao, tiến bộ có thể chậm hơn

    • Cũng có phản biện rằng “có những vấn đề không thể biểu diễn bằng hàm chi phí”
      Ví dụ, việc đưa vào số phức cũng có thể được xem là kết quả của tối ưu hóa biểu diễn

  • Các chuyên gia lĩnh vực đang dạy cho LLM cách họ giải quyết vấn đề của mình
    Cuối cùng LLM sẽ mô phỏng các mẫu hình tư duy đó để giải bài toán

  • Tôi nghĩ có rất nhiều bài toán có thể giải bằng cách lấy mẫu lại các chứng minh hiện có
    Những vòng lặp tìm kiếm mà con người sẽ phát điên lên nếu phải làm thì máy móc có thể kiên trì thực hiện
    Không phải bước tiến lớn, nhưng nó có thể đóng vai trò biến phỏng đoán thành định lý

    • Vấn đề là liệu chứng minh đó có ý nghĩa hay không. Phần lớn có lẽ chỉ là sự lặp lại bên trong một hệ hình sẵn có
      Trường hợp thật sự mở ra một góc nhìn hoàn toàn mới là hiếm
      Cũng có thể chỉ là lãng phí token
    • Tôi nghĩ mọi khám phá đều là kết quả của sự tổng hợp tổ hợp. Gần như không có gì xuất hiện từ hư vô tuyệt đối
    • Vậy thì nên thiết kế benchmark như thế nào để đánh giá ‘tính mới thực sự’, tôi thấy rất tò mò

  • Trang Open Problems của Epoch có 15 bài toán và phân loại độ khó
    Bài vừa được giải lần này thuộc mức ‘moderately interesting’, tức là nằm về phía dễ nhất
    Dù vậy, việc đây là bài toán đã được công khai từ trước khi giải vẫn rất đáng chú ý
    Tôi tò mò không biết 3 bài còn lại cùng cấp độ đó sẽ được giải nhanh đến mức nào

    • Tôi nghĩ việc bất kỳ bài toán nan giải nào được LLM giải quyết đã là sự kiện ở tầm khoa học viễn tưởng rồi

  • Tiêu đề hơi dễ gây hiểu nhầm
    Tiêu đề thực tế là “A Ramsey-style Problem on Hypergraphs”, và không chỉ GPT‑5.4 mà nhiều mô hình hiện đại khác cũng đã giải được
    Dù vậy, đây vẫn là một thành tựu ấn tượng