SẮP XẾP KHI CÓ NHỮNG PHÉP SO SÁNH BỊ CẤM, MÀ VẪN GẦN NHANH NHƯ THƯỜNG
Để sắp xếp n phần tử theo thứ tự bằng cách so sánh chúng từng cặp một, khoảng n log n phép so sánh vừa là cần thiết vừa là đủ. Nhưng điều đó giả định rằng hai phần tử bất kỳ đều có thể so sánh với nhau.
Thường thì không được như vậy. Các tác giả mượn một ví dụ từ một bài báo năm 2011: nhiều ứng viên nộp đơn cho cùng một công việc, mỗi người có những người giới thiệu. Hai ứng viên chỉ có thể được so sánh nếu có một người giới thiệu nào đó biết cả hai. Các phép so sánh được phép tạo thành một mạng lưới, một đồ thị: mỗi phần tử là một điểm, mỗi phép so sánh được phép là một liên kết. Thứ tự thật bị ẩn, nhưng đồ thị được bảo đảm là chứa nó, dưới dạng một đường đi nối mỗi phần tử với phần tử kế tiếp. Câu hỏi đặt ra: cần bao nhiêu phép so sánh để khôi phục thứ tự đó? Đây là bài toán sắp xếp tổng quát (generalized sorting).
Vì sao các mẹo quen thuộc thất bại
Các thuật toán kinh điển dựa vào sự tự do lựa chọn. QuickSort chọn một “chốt” (pivot) và so sánh nó với phần lớn các phần tử khác, nhưng một đồ thị tùy ý có thể không có phần tử nào được nối với phần lớn các phần tử còn lại. MergeSort chia các phần tử thành các nhóm và sắp xếp từng nhóm, nhưng một nhóm có thể không tự sắp xếp được: hai phần tử đứng cạnh nhau trong thứ tự cuối cùng không nhất thiết được nối với nhau bên trong nhóm đó. Sâu xa hơn, việc sắp xếp thông thường luôn có sẵn một phép so sánh loại bỏ được một phần đáng kể các thứ tự khả dĩ; với các phép so sánh bị hạn chế, có thể không có phép nào như vậy.
Tiến bộ đến chậm. Năm 2011, Zhiyi Huang, Sampath Kannan và Sanjeev Khanna tìm ra một phương pháp dùng khoảng n¹·⁵ phép so sánh, nếu bỏ qua các thừa số logarit, và cận đó vẫn đứng vững cho các đồ thị tùy ý kể từ đó. Họ thậm chí còn đặt câu hỏi liệu bài toán có khó hơn sắp xếp thông thường về bản chất hay không, tức là cần tới n lũy thừa một số mũ lớn hơn 1.
Dự đoán trước, sửa chữa sau
Sanjeev Khanna, ở Đại học New York, Aaron Putterman, ở Đại học Harvard, và Junkai Song, cũng ở Đại học New York, nay trả lời câu hỏi đó: không. Thuật toán ngẫu nhiên hóa của họ sắp xếp với trung bình khoảng n log⁴ n phép so sánh, trên bất kỳ đồ thị nào — chỉ hơn sắp xếp thông thường vài thừa số logarit. Và, theo lời họ, nó “tương đối đơn giản”. Tuy vậy, lợi ích này chỉ mang tính lý thuyết: các hằng số trong chứng minh là cực lớn (những thừa số như 2³²), nên ưu thế chỉ lộ rõ khi n rất lớn.
Thuật toán xây dựng trên một kết quả đã biết: nếu ai đó đưa cho bạn một phỏng đoán về chiều của mọi liên kết, sai ở w liên kết trong số đó, thì thứ tự có thể được khôi phục với khoảng n log n + w phép so sánh. Vì vậy, nhiệm vụ trở thành tạo ra một phỏng đoán ít lỗi bằng ít phép so sánh. Các bước then chốt:
- Một phỏng đoán ban đầu thô. So sánh một mẫu ngẫu nhiên gồm các cặp được nối với nhau và chọn một thứ tự bất kỳ phù hợp với các câu trả lời. Phỏng đoán này mắc nhiều lỗi, nhưng không quá nhiều.
- Cô lập các lỗi, thay vì sửa chúng. Thay vì sửa các phỏng đoán sai, thuật toán tìm những phần của đồ thị nơi lỗi dày đặc hơn mức trung bình và gạt chúng sang một bên. Mỗi vòng làm số lỗi còn lại giảm đi bốn lần, tính theo kỳ vọng.
- Quay lại sau. Các liên kết bị gạt sang một bên được xử lý trong một giai đoạn sau. Mỗi giai đoạn giải quyết xong ít nhất một nửa số liên kết còn tồn đọng, nên khoảng hai mươi giai đoạn là đủ cho một triệu liên kết.
Một chứng minh được tìm ra cùng máy móc
Phần công bố về việc sử dụng AI của bài báo chi tiết một cách bất thường. Bài báo nêu rằng ChatGPT 6-Astra “đóng vai trò thiết yếu trong việc chứng minh các cận được cải thiện”. Đầu tiên, một mô hình tìm ra một thuật toán dùng khoảng n¹·³³ phép so sánh, rồi bị chững lại. Các tác giả đẩy nó xuống n¹·²; sau đó, được nhắc lệnh hàng chục lần trong nhiều tuần, các mô hình tìm ra những cải tiến nối tiếp nhau — n^(10/9), n^(17/16), n^(19/18) — trước khi đạt tới thuật toán gần tuyến tính. Các tác giả nói thêm rằng không rõ bước trung gian của chính họ có thiết yếu cho khám phá cuối cùng đó hay không.
Những gì vẫn còn bỏ ngỏ
Kết quả đếm số phép so sánh, chứ không phải thời gian tính toán: như được phát biểu, thuật toán không chạy trong thời gian đa thức, trong khi phương pháp năm 2011 thì có. Các tác giả liệt kê ba câu hỏi mở: liệu có thể loại bỏ các thừa số logarit còn lại hay không, liệu một thuật toán không dùng tính ngẫu nhiên có làm được tốt như vậy hay không, và liệu một thuật toán hiệu quả có đạt được cùng số phép so sánh — hay thậm chí chỉ cần vượt qua được n¹·⁵ — hay không.
