Phó Chủ tịch Google Research Vahab Mirrokni vừa công bố chứng minh của nhóm nghiên cứu Google đối với giả thuyết Courtade - Kumar, một trong những bài toán mở quan trọng của lý thuyết thông tin.

Đáng chú ý, gần như cùng thời điểm, một nhóm nghiên cứu đến từ Việt Nam gồm TS Vũ Khắc Kỷ, công tác tại Trường Đại học FPT, và GS Trần Mạnh Tuấn, công tác tại Đại học Khoa học và Công nghệ Trung Quốc, cũng công bố một chứng minh hoàn chỉnh cho giả thuyết này.

Hai nhóm nghiên cứu hoàn toàn độc lập đã đi đến lời giải bằng những phương pháp khác nhau.

Bài toán hơn một thập kỷ chưa có lời giải tổng quá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 truyền tin và xử lý thông tin: Khi dữ liệu bị nhiễu trên đường truyền, cách lựa chọn và xử lý thông tin ban đầu như thế nào sẽ giúp giữ lại nhiều thông tin nhất?

Điều đáng chú ý là giả thuyết đưa ra một đáp án khá đơn giản: thay vì kết hợp nhiều bit theo một quy tắc phức tạp, chiến lược tối ưu là chỉ giữ lại một bit duy nhất.

Tuy nhiê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 khi lời giải tổng quát vẫn là một thách thức.

TS Vũ Khắc Kỷ hiện công tác tại Trường Đại học FPT. Ông cho biết khoảng 10 năm trước, khi đang làm nghiên cứu sau tiến sĩ tại Đại học Trung văn Hồng Kông (CUHK), ông được GS Chandra Nair giới thiệu về giả thuyết này.

Sau đó, TS Kỷ dành khoảng 2 năm theo đuổi bài toán nhưng chưa tìm được lời giải. Từ tháng 1/2019, ông nhiều lần quay lại nghiên cứu, song đều phải tạm dừng do chưa tìm được cơ chế đủ mạnh để vượt qua những rào cản đã biết.

Đến năm 2025, TS Kỷ bắt đầu nghiên cứu lại bài toán một cách nghiêm túc hơn. Trong giai đoạn này, ông hợp tác với GS Trần Mạnh Tuấn, chuyên gia về xác suất rời rạc và tổ hợp.

Hai hướng nghiên cứu bổ trợ cho nhau, giúp các tác giả liên tục kiểm tra, loại bỏ và hoàn thiện các ý tưởng. Nhóm từng bước mở rộng miền kiểm soát, xử lý những trường hợp còn lại và tiến tới chứng minh cho trường hợp tổng quát.

Hai lời giải xuất hiện gần như đồng thời

Ngày 21/9, bài báo “Dictators are most informative” của TS Vũ Khắc Kỷ và GS Trần Mạnh Tuấ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.

Trước khi công bố bài báo, TS Kỷ chủ động gửi email cho GS Chandra Nair để thông báo về kết quả nghiên cứu, như một cách thể hiện sự tôn trọng đối với người từng giới thiệu bài toán cho ông.

Theo chia sẻ của TS Kỷ, GS Chandra Nair phản hồi rằng nhóm của ông, cùng các nhà khoa học đến 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 cùng giả thuyết.

Sau đó, ông Vahab Mirrokni, Phó Chủ tịch Google Research và 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, công bố kết quả của nhóm Google, đồng thời gửi lời chúc mừng tới nhóm nghiên cứu đến từ Việt Nam.

Việc hai nhóm nghiên cứu độc lập gần như đồng thời hoàn thành chứng minh cho cùng một bài toán, bằng hai hướng tiếp cận khác nhau, đánh dấu một bước tiến đáng chú ý trong quá trình giải quyết giả thuyết Courtade - Kumar.