Đột phá thuật toán: 3SUM và APSP lần đầu được giải dưới ngưỡng bậc hai và bậc ba

Trong thế giới khoa học máy tính lý thuyết, một số giả thuyết độ phức tạp đã tồn tại như những "định luật bất thành văn" suốt nhiều thập kỷ. Mới đây, hai nhà nghiên cứu Josh Alman và Virginia Vassilevska Williams đã công bố một kết quả gây chấn động: họ tìm ra thuật toán đầu tiên thực sự vượt qua ngưỡng bậc hai cho bài toán 3SUM và ngưỡng bậc ba cho bài toán đường đi ngắn nhất toàn cặp (APSP).

Bài toán 3SUM và APSP là gì?

3SUM là bài toán kinh điển: cho một tập hợp gồm n số nguyên, hãy xác định xem có tồn tại ba số nào cộng lại bằng 0 hay không. Thuật toán "sách giáo khoa" quen thuộc từ lâu vẫn chạy trong thời gian bậc hai, tức O(n²).

APSP (All-Pairs Shortest Paths) — bài toán tìm đường đi ngắn nhất giữa mọi cặp đỉnh trong đồ thị — cũng có thuật toán nền tảng chạy trong thời gian bậc ba O(n³).

Điều đặc biệt là cả hai bài toán này từ lâu được xem là "chuẩn mực" để đánh giá độ khó của hàng loạt bài toán khác. Nếu giải nhanh được 3SUM, người ta có thể suy ra thuật toán nhanh hơn cho rất nhiều vấn đề khác.

Cú đột phá phá vỡ giả thuyết

Theo bài báo trên arXiv, nhóm nghiên cứu đã:

• Giải quyết bài toán 3SUM trên n số nguyên có kích thước đa thức trong thời gian O(n^1.9992) — lần đầu tiên xuống dưới bậc hai một cách thực sự.
• Giải quyết APSP trên đồ thị có hướng n đỉnh với trọng số nguyên bị chặn đa thức trong thời gian O(n^2.9995) — lần đầu tiên xuống dưới bậc ba.

Đây là lần đầu tiên con người đạt được cải thiện đa thức so với các thuật toán sách giáo khoa cho cả hai bài toán này.

Kết quả này trực tiếp bác bỏ Giả thuyết 3SUM và Giả thuyết APSP — hai giả thuyết được cộng đồng tin tưởng suốt nhiều năm như những chân lý nền tảng.

Bí quyết nằm ở phép nhân ma trận "mỏng"

Điểm mấu chốt của công trình là một thuật toán mới cho tích ma trận mỏng (thin matrix products). Cụ thể, với ma trận X kích thước N×D và ma trận Y kích thước D×N, trong đó D nhỏ hơn nhiều so với N, nhóm nghiên cứu chỉ tính đúng những phần tử cần thiết tại một tập vị trí W cho trước, thay vì tính toàn bộ tích ma trận.

Cách tiếp cận này được xây dựng dựa trên thuật toán nhân ma trận chữ nhật của Coppersmith và một định thức nhân mười của Schönhage, nhưng được tinh chỉnh để chỉ thực hiện các phép toán thật sự cần thiết.

Khi diễn giải dưới góc độ đồ thị, thuật toán này giải được bài toán tam giác thưa trên mọi cạnh (All-Edges Sparse Triangle) trong thời gian thực sự dưới bậc hai, áp dụng cho các đồ thị ba phần "lệch" thưa.

Hệ quả dây chuyền cho khoa học máy tính

Thành tựu này không dừng lại ở hai bài toán gốc. Nhờ các phép quy dẫn đã biết, nhóm nghiên cứu còn bác bỏ thêm nhiều giả thuyết quan trọng:

• Phiên bản số thực của Giả thuyết 3SUM và Giả thuyết APSP
• Giả thuyết Tam giác chính xác (Exact Triangle)
• Giả thuyết Zero-Weight k-Clique
• Ba phỏng đoán Online Matrix–Vector dạng chữ nhật của van den Brand, Nanongkai và Saranurak

Ngoài ra, họ còn đưa ra tốc độ tăng đa thức cho hàng loạt bài toán khác trong lĩnh vực thuật toán.

Vì sao tin này quan trọng với giới công nghệ?

Với độc giả công nghệ Việt Nam, kết quả này có ý nghĩa thực tiễn lâu dài. Các bài toán như 3SUM và APSP xuất hiện ngầm trong nhiều hệ thống thực tế:

• Hệ thống định tuyến mạng và tối ưu hạ tầng đám mây
• Công cụ tìm kiếm và truy vấn dữ liệu lớn
• Thuật toán đồ thị trong phân tích mạng xã hội và phát hiện gian lận
• Tối ưu hóa logistics và chuỗi cung ứng

Mặc dù tốc độ cải thiện nghe có vẻ nhỏ (từ lũy thừa 2 xuống 1.9992), trong lý thuyết độ phức tạp, việc vượt qua một ngưỡng bậc là cột mốc mang tính bước ngoặt — tương tự như việc lần đầu tiên bơi được qua một eo biển tưởng chừng bất khả thi.

Việc hai tác giả Alman và Vassilevska Williams — những tên tuổi hàng đầu về thuật toán — đứng sau công trình này càng khiến cộng đồng nghiên cứu quốc tế chú ý. Trên diễn đàn Hacker News, bài báo nhanh chóng thu hút thảo luận sôi nổi, phản ánh mức độ quan tâm của giới kỹ sư và nhà nghiên cứu toàn cầu.