Bài toán hơn 10 năm thách thức giới toán học và khoa học máy tính
Theo thông tin trường ĐH FPT xác nhận thông tin, nhóm nghiên cứu gồm TS Vũ Khắc Kỷ (giảng viên bộ môn Toán, trường ĐH FPT) và GS Trần Mạnh Tuấn (Đại học Khoa học và Công nghệ Trung Quốc) đã tìm ra chứng minh hoàn chỉnh cho giả thuyết Courtade-Kumar - một trong những bài toán mở quan trọng nhất của lý thuyết thông tin.
Thông tin này cũng đã được ông Vahab Mirrokni, Phó Chủ tịch Google Research, người lãnh đạo các nhóm nghiên cứu về Thuật toán và Tối ưu hóa tại Google, ghi nhận và chúc mừng. Sự kiện này khẳng định năng lực của các nhà khoa học Việt Nam trong việc tham gia giải quyết trực tiếp các bài toán nền tảng mang tầm quốc tế.
Giả thuyết Courtade-Kumar, còn được gọi là “Most Informative Boolean Function Conjecture”, được Thomas Courtade và Gowtham Kumar đề xuất năm 2013. Bài toán xuất phát từ một câu hỏi trong lý thuyết thông tin: khi dữ liệu được truyền qua một kênh có nhiễu, cách lựa chọn và xử lý thông tin ban đầu như thế nào để lượng thông tin được giữ lại ở đầu ra là lớn nhất?
Điểm đáng chú ý của giả thuyết là câu trả lời được dự đoán lại khá đơn giản: chiến lược tối ưu là chỉ giữ lại một bit đầu vào, thay vì kết hợp nhiều bit theo một quy tắc phức tạp. Tuy nhiên, việc chứng minh nhận định này không đơn giản. Trong hơn một thập kỷ, các nhà toán học trên thế giới mới chỉ giải được một số trường hợp riêng của bài toán.
Trong bài viết công bố kết quả, ông Mirrokni gọi Courtade-Kumar là một “bài toán mở trung tâm tồn tại lâu năm ở giao điểm giữa lý thuyết thông tin và giải tích hàm Boolean”. Ông cũng nhắc lại rằng trong chuyên khảo của Yu và Tan, giả thuyết này được mô tả là “một trong những bài toán mở quan trọng nhất của lý thuyết thông tin”.
Hai nhóm nghiên cứu từ Việt Nam và Google cùng đi tới kết quả
Điều đặc biệt là gần như cùng thời điểm, hai nhóm nghiên cứu hoàn toàn độc lập là 2 nhà nghiên của Việt Nam và nhóm 7 nhà nghiên cứu trên thế giới khác đã đều đi đến lời giải bằng hai con đường rất khác nhau.TS Vũ Khắc Kỷ cho biết, khoảng 10 năm trước, khi làm nghiên cứu sau tiến sĩ trong nhóm Information Theory tại Đại học Trung văn Hồng Kông, Trung Quốc (Chinese University of Hong Kong - CUHK), ông đã được GS Chandra Nair kể cho về giả thuyết này.
Nhà khoa học người Việt đã theo đuổi nó khá nghiêm túc trong khoảng hai năm nhưng không thành công. Từ tháng 1/2019, sau khi về trường ĐH FPT giảng dạy, ông vẫn thỉnh thoảng quay lại bài toán nhưng mỗi lần làm một thời gian rồi lại phải dừng vì chưa tìm được một cơ chế đủ mạnh để vượt qua các rào cản đã biết.
Đến năm 2025, TS Kỷ bắt đầu quay lại bài toán một cách nghiêm túc hơn. Ông hợp tác với GS Trần Mạnh Tuấn, hiện là GS được bổ nhiệm đặc biệt tại Đại học Khoa học và Công nghệ Trung Quốc, một chuyên gia hàng đầu thế giới về xác suất rời rạc và tổ hợp. Hai hướng nghiên cứu bổ trợ cho nhau. Các công cụ từ tổ hợp, xác suất và cấu trúc rời rạc của GS Tuấn bổ sung hiệu quả cho hướng entropy và giải tích mà TS Kỷ đang theo đuổi, giúp hai tác giả liên tục kiểm tra, loại bỏ và cải thiện các ý tưởng. Theo TS Kỷ, trí tuệ nhân tạo cũng được sử dụng trong quá trình nghiên cứu, nhưng không thay thế việc xây dựng chứng minh toán học.
Bài báo “Dictators are most informative” do 2 nhà nghiên cứu thực hiện đã được đưa lên arXiv - kho lưu trữ trực tuyến dành cho các tiền ấn phẩm khoa học vào ngày 21/9. Công trình chứng minh giả thuyết cho mọi hàm Boolean, bao gồm cả trường hợp không cân bằng. Điều đáng chú ý là gần như cùng thời điểm, một nhóm nghiên cứu quốc tế cũng hoàn thành chứng minh cho cùng bài toán.
Trước khi công bố công trình, TS Kỷ chủ động gửi email cho GS Chandra Nair - người 10 năm trước giới thiệu với ông về bài toán này - để thông báo rằng ông và GS Trần Mạnh Tuấn đã tìm được lời giải.
GS Nair phản hồi rằng nhóm của ông, cùng các nhà khoa học từ Google và một số trường đại học khác, cũng vừa hoàn thành một chứng minh cho giả thuyết Courtade-Kumar. Sau khi trao đổi, hai bên nhận ra họ đã độc lập đi đến cùng một kết quả nhưng bằng hai phương pháp rất khác nhau.
Bản thảo của nhóm bảy người trên thế giới dài hơn 250 trang, trong khi bài của hai nhà nghiên cứu Việt Nam chỉ khoảng 36 trang. Tuy nhiên, số trang không nói lên lời giải nào tốt hơn; mỗi cách tiếp cận đều có những điểm mạnh riêng và cần được cộng đồng toán học đánh giá theo thời gian.
Nhưng sau khi biết kết quả của nhau, vì nhóm của GS Nair cần thêm thời gian để hoàn thiện một công trình dài chứa nhiều tính toán, TS Kỷ và GS Tuấn đã quyết định lùi thời điểm công bố của mình và thống nhất công bố hai lời giải độc lập trong cùng thời điểm. “Với tôi, đây cũng là một câu chuyện đẹp của nghiên cứu khoa học”, TS Vũ Khắc Kỷ chia sẻ.
