GIỚI HẠN TỐC ĐỘ TÌM CLIQUE SỤP ĐỔ SAU 40 NĂM
Hãy hình dung một mạng xã hội với n người. Có tồn tại một nhóm k người trong số đó đều quen biết lẫn nhau không? Các nhà khoa học máy tính gọi một nhóm như vậy là k-clique, và tìm ra một nhóm như thế là một bài toán kinh điển với vô số ứng dụng. Cách làm ngây thơ là kiểm tra mọi nhóm k người có thể có, khoảng n^k nhóm — vô vọng với các mạng lưới lớn.
Một mẹo từ năm 1985 và một thách thức kéo dài
Hơn 40 năm trước, Jaroslav Nešetřil và Svatopluk Poljak đã tìm ra một lối tắt. Họ biến việc tìm một k-clique thành việc tìm một tam giác trong một đồ thị lớn hơn, điều mà đến lượt nó có thể thực hiện bằng cách nhân ma trận, tức những bảng số lớn. Chi phí phụ thuộc vào ω, số mũ của phép nhân ma trận: phương pháp của họ mất khoảng n^(ωk/3) bước. Không ai biết chính xác ω. Nó ít nhất bằng 2, và bài báo trích dẫn một cận trên gần đây là 9/4.
Số mũ của phương pháp năm 1985 ấy chưa bao giờ bị vượt qua. Năm 2004, Gerhard Woeginger thách thức các nhà nghiên cứu làm tốt hơn với một giá trị k cố định nào đó; hơn hai thập kỷ đã trôi qua. Trong khi đó, Giả thuyết k-Clique — rằng n^(ωk/3) về cơ bản là tốt nhất có thể — trở thành một nền móng của “độ phức tạp chi tiết” (fine-grained complexity). Các nhà nghiên cứu dùng nó để lập luận rằng nhiều bài toán khác, từ phân tích cú pháp văn phạm đến phân tích dữ liệu nén, cũng không thể giải nhanh hơn.
Một mục tiêu di động
Bác bỏ giả thuyết này có một khó khăn đặc biệt. Chi phí mà nó dự đoán phụ thuộc vào ω, vốn chưa được biết. Một thuật toán vượt qua giá trị tốt nhất hiện nay của ω có thể thôi vượt qua giả thuyết nếu sau này có người tìm ra phép nhân ma trận nhanh hơn.
Virginia Vassilevska Williams, của MIT, và Or Zamir, của Đại học Tel Aviv, né được vấn đề này. Họ chứng minh rằng với mọi k đủ lớn, một k-clique có thể được tìm ra — và thậm chí được đếm — trong khoảng n^((ω/3 − c)k) bước, trong đó c là một hằng số dương không phụ thuộc vào k lẫn ω. Mức tiết kiệm được đo so với giá trị thật của ω, dù nó hóa ra là bao nhiêu. Nó vẫn còn ngay cả khi ω = 2, trường hợp tốt nhất có thể hình dung.
Gấp một hình nêm
Trái tim của phương pháp liên quan đến các mẫu gồm chín đỉnh. Cách tiếp cận tiêu chuẩn chia chúng thành ba nhóm ba đỉnh và nhân ba ma trận khổng lồ. Các tác giả xem xét một hình nêm (wedge) — hai cạnh có chung một đỉnh — và chèn, giữa hai trong số các ma trận, một bảng không làm thay đổi gì: ma trận đơn vị. Sau đó họ viết ma trận đơn vị ấy thành tổng của một vài “phép hoán đổi” (swaps), mỗi phép hợp nhất hai cạnh của hình nêm thành một, cộng với một phần dư có hạng thấp.
Các phép hoán đổi cho ra những mẫu đơn giản hơn với ít cạnh hơn, được xử lý lại bằng chính phương pháp đó; một mẫu chín đỉnh có tối đa 36 cạnh, nên phép đệ quy sẽ kết thúc. Phần dư hạng thấp làm thu nhỏ các ma trận cần nhân. Áp dụng mẹo này cho hai hình nêm tách biệt cùng lúc chính là điều giữ được lợi thế ngay cả khi ω = 2. Khi đó, mọi k là bội số của chín đều có thể được gom thành chín khối.
Có thật nhưng rất nhỏ
Các tác giả không đưa ra con số cho mức lợi. Họ mô tả các hằng số nằm trong khoảng “từ cực kỳ nhỏ khi không tối ưu hóa đến rất nhỏ khi tối ưu hóa đáng kể”. Mục đích không phải là tốc độ trong thực tế: mà là một rào cản được tin suốt nhiều thập kỷ hóa ra không tồn tại.
Hệ quả vượt ra ngoài các clique. Các thuật toán chính xác cho những bài toán tối ưu hóa khó như Max-Cut và Max-2-SAT, vốn chạy trong khoảng 2^(ωn/3) bước với n biến, nay cũng có số mũ nhỏ hơn. Việc đếm số bản sao của bất kỳ đồ thị nhỏ cố định nào cũng vậy.
AI đã làm gì
Trong một phần riêng, các tác giả mô tả cách họ làm việc với ChatGPT-6, được sử dụng qua giao diện web công khai của nó. Xuất phát từ những ý tưởng của chính họ cho clique năm người và từ một kết quả gần đây của OpenAI bác bỏ một phỏng đoán khác, Giả thuyết Thời gian Mũ (Exponential Time Hypothesis), mô hình đã tìm ra một cải tiến đầu tiên, phức tạp, cho 5-clique. Các tác giả sau đó chắt lọc nó, với sự trợ giúp của AI, thành phép phân tích đại số nằm ở lõi của chứng minh, mà họ xem là “gần như thuần túy là đóng góp của AI”. Khung thuật toán được xây dựng xung quanh nó, theo lời họ, chủ yếu là của họ.
Có một nhận xét nổi bật. Các chứng minh tối nghĩa do AI tạo ra rất khó để con người đọc, các tác giả lưu ý — và họ “ấn tượng khi thấy chúng cũng khó hiểu với chính AI”.
