RÀO CẢN TỪ NĂM 1962 TRONG KHOA HỌC MÁY TÍNH ĐÃ SỤP ĐỔ

Một chu trình Hamilton là một hành trình khép kín qua một mạng lưới, đi qua mọi điểm đúng một lần rồi trở về điểm xuất phát. Trong một mạng có hướng, mỗi liên kết là một mũi tên chỉ có thể đi theo một chiều, giống như đường một chiều. Phiên bản có trọng số của bài toán này là bài toán người bán hàng du lịch bất đối xứng.

Quyết định xem một chu trình như vậy có tồn tại hay không là một bài toán khó kinh điển trong sách giáo khoa. Năm 1962, Richard Bellman và, một cách độc lập, Michael Held cùng Richard Karp đã đưa ra các thuật toán quy hoạch động giải nó trong thời gian khoảng 2ⁿ cho một mạng gồm n điểm (bỏ qua các thừa số chỉ tăng theo đa thức). Suốt hơn sáu mươi năm, không ai làm tốt hơn một cách căn bản trên các mạng có hướng tổng quát.

Người anh em vô hướng đã gục ngã từ trước

Với các mạng có liên kết hai chiều, Andreas Björklund đã phá vỡ rào cản vào năm 2014 bằng một thuật toán ngẫu nhiên chạy trong 1,657ⁿ, công trình đã mang về cho ông Giải Nerode EATCS–IPEC năm 2016, theo bài báo. Đến nay đó vẫn là thuật toán nhanh nhất được biết cho các mạng vô hướng tổng quát. Với mạng có hướng, tiến bộ chỉ đến ở những trường hợp đặc biệt — mạng hai phía, mạng có ít liên kết ở mỗi điểm — hoặc dưới một giả thuyết chưa được chứng minh, giả thuyết hạng tiệm cận của Strassen.

Cận mới

Tomohiro Koana, ở Đại học Tokyo, và Soh Kumabe, ở công ty CyberAgent tại Tokyo, nay đưa ra một thuật toán ngẫu nhiên quyết định bài toán có hướng trong thời gian

O((375/196)ⁿ) = O(1,9133ⁿ)**.

Với các mạng có hướng tổng quát, đây là cải tiến đầu tiên ở cơ số của hàm mũ kể từ năm 1962.

Đếm chẵn và lẻ

Cái khó ở đây rất tinh tế. Việc đếm các chu trình theo modulo 2 — chỉ biết số lượng của chúng là lẻ hay chẵn — vốn đã làm được dưới 2ⁿ. Nhưng một số chẵn khác không các chu trình trông y hệt như số không. Cách khắc phục kinh điển là gán cho các liên kết những trọng số ngẫu nhiên để, ở một tổng trọng số nào đó, lời giải trở nên duy nhất (bổ đề cô lập, isolation lemma); nhưng phương pháp đếm tính chẵn lẻ nhanh lại không xử lý được trọng số.

Công thức của các tác giả, nói bằng lời đơn giản:

1. Đoán một mũi tên của chu trình, và thay vào đó tìm một đường đi qua mọi điểm từ đầu này đến đầu kia của mũi tên đó.
2. Xóa mỗi mũi tên một cách ngẫu nhiên với xác suất 1/50.
3. Tại mỗi điểm, tạo ba nhóm mũi tên đi vào, và sao chép mỗi mũi tên còn lại vào một tập hợp nhóm ngẫu nhiên khác rỗng.
4. Nếu hành trình tồn tại, thì với xác suất ít nhất (49/50)ⁿ⁻¹ ta có thể chọn một nhóm cho mỗi điểm sao cho số đường đi hợp lệ là lẻ.
5. Gán cho mỗi nhóm — chứ không phải mỗi mũi tên — một trọng số ngẫu nhiên. Giờ mẹo cô lập phát huy tác dụng, và khoảng (50/49)ⁿ lần lặp là đủ.
6. Mỗi lần lặp tính số đếm chẵn hay lẻ ở mọi tổng trọng số trong thời gian (15/8)ⁿ, dùng các tổng định thức ma trận của Björklund, Kaski và Koutis cùng một phép “tuyến tính hóa” ngẫu nhiên cũng được Arvind và Guruswami sử dụng.

Nhân hai thứ đó lại: (50/49)ⁿ × (15/8)ⁿ = (375/196)ⁿ ≈ 1,9133ⁿ.

Một chứng minh do máy tạo ra

Bài báo kết thúc bằng một tuyên bố về AI tạo sinh: ChatGPT 6 Astra đã tạo ra chứng minh của định lý chính và giúp soạn thảo bản thảo. Các tác giả cung cấp phát biểu của các mệnh đề trung gian, vốn đưa ra một cách đọc tổ hợp cho lời giải ban đầu của mô hình, sau đó kiểm tra và chỉnh sửa mọi thứ và chịu hoàn toàn trách nhiệm.

Kết quả này mang tính lý thuyết — không có chương trình nào được chạy — và thuật toán là ngẫu nhiên, với một khả năng nhỏ mắc lỗi theo cả hai chiều. Giữa 1,9133 cho đường một chiều và 1,657 cho đường hai chiều, vẫn còn một khoảng cách lớn để ngỏ.