Nhà toán học Việt tìm ra lời giải cho bài toán tồn tại hơn một thập kỷ

Vừa qua, ô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, đã công bố chứng minh của nhóm Google 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.

Bên cạnh đó, ông Vahab Mirrokni cũng chúc mừng 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 thu được một chứng minh hoàn chỉnh cho giả thuyết này.

Điều đặc biệt, gần như cùng thời điểm, hai nhóm nghiên cứu hoàn toàn độc lập đã đi đến lời giải bằng hai con đường rất khác nhau.

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 rất tự nhiên trong truyền tin và xử lý thông tin, khi dữ liệu bị nhiễu trên đường truyền, ta nên chọn và xử lý thông tin ban đầu theo cách nào để sau cùng vẫn giữ lại được nhiều thông tin nhất?

Điều bất ngờ, giả thuyết cho rằng chiến lược tối ưu lại cực kỳ đơn giản. Thay vì kết hợp nhiều bit theo một quy tắc phức tạp, chỉ cần 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 từng trường hợp riêng của bài toán.

TS Vũ Khắc Kỷ hiện công tác tại Trường Đại học FPT.

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ĩ tại Đại học Trung văn Hồng Kông, Trung Quốc (CUHK), ông từng được GS Chandra Nair kể cho về giả thuyết này.

Sau đó, ông đã theo đuổi nghiêm túc trong khoảng 2 năm nhưng không thành công. Từ tháng 1/2019, ô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. Cũng trong giai đoạn đó, ông bắt đầu hợp tác với GS Trần Mạnh Tuấn, một chuyên gia về xác suất rời rạc và tổ hợp.

Hướng nghiên cứu của cả hai đã bổ trợ cho nhau, 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. Nhóm nghiên cứu từng bước mở rộng miền kiểm soát được, xử lý các trường hợp còn lại và cuối cùng đi tới chứng minh cho trường hợp tổng quát.

Đến ngày 21/9, bài báo “Dictators are most informative” của hai nhà khoa học này đã đượ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 bài báo được công bố, để bày tỏ sự tôn trọng, TS Kỷ đã chủ động email cho GS Chandra Nair để thông báo rằng anh và cộng sự đã tìm được lời giải.

“GS Chandra Nair trả lờ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 cùng bài toán”, TS Kỷ chia sẻ.

Hai nhóm sau đó trao đổi và nhận ra rằng họ đã độc lập đi đến cùng một kết quả bằng hai phương pháp rất khác nhau. Mỗi cách tiếp cận đều có những điểm mạnh riêng, song vẫn 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. Kỷ chia sẻ.