CHỌN NHỮNG SỐ CỘNG LẠI ĐÚNG ĐÍCH, GẦN NHƯ NHANH BẰNG VIỆC ĐỌC CHÚNG

Đây là một câu đố ai cũng có thể phát biểu. Bạn có một danh sách số nguyên — chẳng hạn 3, 9, 14, 20 — và một giá trị đích, chẳng hạn 23. Bạn có thể chọn vài số sao cho chúng cộng lại đúng bằng giá trị đích không? (Ở đây là có: 3 + 20 hoặc 9 + 14.) Đó là bài toán Tổng tập con (Subset Sum), một trong những bài toán cơ bản nhất của khoa học máy tính. Bài báo mô tả nó là một bài toán NP-đầy đủ cơ bản, thuộc một họ bài toán nổi tiếng là khó giải chính xác.

Tuy vậy vẫn có một kẽ hở. Nếu các số không quá lớn, các thuật toán khéo léo chạy trong thời gian phụ thuộc vào độ lớn của chúng. Phương pháp kinh điển, của Bellman năm 1957, mất thời gian tỉ lệ với số lượng số n nhân với giá trị đích t. Từ đó, các thuật toán liên tục được cải tiến:

• Pisinger (1999): tỉ lệ với n × N, trong đó N là số lớn nhất;
• Bringmann (2017): xấp xỉ n + t;
• nhiều nhóm (2021–2024): xấp xỉ n + N^(5/3), rồi n + N^(3/2).

Chén thánh là thời gian xấp xỉ n + N — không hơn bao nhiêu so với việc đọc dữ liệu đầu vào. Các nhà nghiên cứu trong lĩnh vực từng gọi đó là “bài toán mở then chốt nhất” của hướng nghiên cứu này.

Chỉ còn cách đích một sợi tóc

Lin Chen, Yuchen Mao và Guochuan Zhang, thuộc Đại học Chiết Giang ở Trung Quốc, đưa ra một thuật toán chạy trong thời gian n + N^(1+ε), trong đó ε có thể là bất kỳ số dương nhỏ nào được cố định trước — 0,1, 0,01, 0,001. Thuật toán là tất định, chấp nhận số âm và giá trị lặp lại, và đi kèm một chứng minh toán học. Các tác giả gọi thời gian này là gần tối ưu.

Kết quả mở rộng được cho vectơ: chọn các phần tử sao cho nhiều tổng cùng lúc đạt đích của chúng, với thời gian N^(d+ε) cho d tọa độ. Điều đó, đến lượt nó, trả lời một phần câu hỏi mà nhiều nhóm đã đặt ra về quy hoạch nguyên — tìm nghiệm số nguyên cho các hệ phương trình có biến bị chặn. Hai hệ quả được trình bày tường minh: chia một tập số thành hai nửa bằng nhau, và phân việc giữa hai máy giống hệt nhau đều nhất có thể.

Nâng các con số lên chiều cao hơn

Ý tưởng then chốt mang tính hình học. Người ta đã biết rằng bài toán dễ khi các số dày đặc và giá trị đích nằm sâu bên trong khoảng các tổng khả dĩ. Nhận xét của các tác giả: một tập số thưa có thể trông dày đặc khi nhìn từ một chiều cao hơn.

Ví dụ của họ là tập {11, 12, 22, 24}. Viết 11 và 22 thành một bước và hai bước dọc theo trục thứ nhất, và 12 và 24 thành một bước và hai bước dọc theo trục thứ hai. Khi đó các tổng khả dĩ lấp đầy mọi điểm của một hình vuông nhỏ 4 nhân 4. Nhưng ép hình vuông đó trở lại một đường thẳng — bằng cách tính 11x + 12y — thì các tổng tạo thành bảy cụm tách biệt có khoảng trống giữa chúng, rải rác giữa 0 và 69. Các khoảng trống là ảo giác của phép chiếu; trong hai chiều, cấu trúc rất đơn giản.

Thuật toán xây dựng những tọa độ nhiều chiều như vậy cho bất kỳ đầu vào nào, dùng các kết quả từ tổ hợp cộng tính (additive combinatorics). Bên trong vùng “đã lấp đầy”, câu trả lời có được miễn phí. Chỉ một dải mỏng gần biên mới cần làm việc thực sự, và thuật toán chia nó thành các bài toán nhỏ hơn rồi giải đệ quy. Mỗi vòng thu hẹp dải đó rất mạnh, và số chiều mới được thêm vào luôn chỉ là một hằng số.

Chứng minh được xây dựng thế nào

Bài báo mở đầu bằng một “tuyên bố về AI”. Các tác giả tự thiết kế lộ trình chứng minh chính, dựa trên công trình gần đây của chính họ về các phiên bản dày đặc, nhiều chiều của bài toán. Sau đó họ dùng một mô hình AI, GPT Astra Ultra, để biến những ý tưởng này thành các chứng minh toán học hoàn chỉnh. Mô hình bị mắc kẹt ở vài bổ đề, vốn được giải quyết bằng ý tưởng của các tác giả; một ghi chú nghiên cứu công khai lưu lại các cuộc trao đổi. Khi thuật toán ngẫu nhiên cơ bản hoàn tất, mô hình đã mở rộng nó sang các phiên bản tất định, nhiều chiều “mà không có bất kỳ hướng dẫn nào từ các tác giả”. Mô hình cũng soạn thảo bài báo và, theo lời các tác giả, đã kiểm chứng các kết quả chính bằng một chứng minh trong trợ lý chứng minh Lean 4. Các tác giả chịu hoàn toàn trách nhiệm về nội dung.

Chưa hẳn là vạch đích

Số mũ là 1 + ε chứ không đúng bằng 1, và các hằng số ẩn tăng lên khi ε nhỏ đi; sự phụ thuộc vào số chiều chưa được tối ưu. Chính các tác giả mô tả thuật toán là “khá phức tạp”. Bài báo mang tính lý thuyết: nó không báo cáo cài đặt hay phép đo hiệu năng nào.