TS Vũ Khắc Kỷ và GS Trần Mạnh Tuấn công bố chứng minh hoàn chỉnh cho giả thuyết Courtade – Kumar (CK), bài toán mở quan trọng của lý thuyết thông tin. Lời giải được hai nhà nghiên cứu đăng trên nền tảng arXiv ngày 21/9.
Lời giải của hai nhà nghiên cứu được đăng trên arXiv ngày 21/9. Gần như cùng thời điểm, ông Vahab Mirrokni, Phó Chủ tịch Google Research, cũng công bố một chứng minh cho giả thuyết CK bằng phương pháp khác. Hai nhóm nghiên cứu làm việc độc lập nhưng cùng đi đến một kết quả.
Trong bài viết trên mạng xã hội X ngày 22/9, ông Mirrokni cho biết CK 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 dẫn một chuyên khảo mô tả đây là một trong những bài toán mở quan trọng của lý thuyết thông tin. Google Research đã ghi nhận và chúc mừng lời giải độc lập của TS Kỷ cùng cộng sự.
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 Hong Kong, TS Kỷ được giáo sư giới thiệu về giả thuyết CK. Ông dành khoảng hai năm để nghiên cứu nhưng chưa thành công. Sau khi trở về Đại học FPT giảng dạy từ tháng 1/2019, ông vẫn thỉnh thoảng quay lại bài toán, song những rào cản cũ chưa được giải quyết.
Hơn một thập kỷ trở lại với một câu hỏi chưa có lời giải
Bước ngoặt xuất hiện vào năm ngoái, khi TS Kỷ nghiên cứu về hình học thông tin và các công cụ hình học trong học máy. Ông nhận thấy giả thuyết CK có nhiều cấu trúc liên quan đến entropy, mutual information và sự biến đổi của thông tin dưới tác động của nhiễu. Từ hướng tiếp cận này, ông quyết định thử lại bài toán. Ông từng làm việc tại Viện nghiên cứu ITCSC ở Hong Kong trước khi trở về Việt Nam.
Trong quá trình đó, TS Kỷ hợp tác với GS Tuấn, chuyên gia về xác suất rời rạc và tổ hợp. Các công cụ về tổ hợp, xác suất và cấu trúc rời rạc bổ sung cho hướng entropy và giải tích mà TS Kỷ theo đuổi. Hai nhà nghiên cứu liên tục kiểm tra, loại bỏ và cải thiện các ý tưởng để hoàn thiện chứng minh. Theo TS Kỷ, khó khăn lớn nhất nằm ở khoảng cách giữa phát biểu và chứng minh. Bài toán chỉ cần vài dòng để phát biểu nhưng những phương pháp tự nhiên thường chỉ giải được một miền tham số hoặc một lớp hàm đặc biệt.
Có những lúc hai tác giả tưởng đã tiến gần đến lời giải nhưng lại phát hiện một khoảng trống và phải quay lại gần như từ đầu. TS Kỷ cho rằng khả năng kiên trì với một bài toán sau nhiều lần thất bại là yếu tố quan trọng trong hành trình nghiên cứu. TS Kỷ tốt nghiệp cử nhân tài năng Đại học Khoa học Tự nhiên, Đại học Quốc gia Hà Nội năm 2009, sau đó học thạc sĩ tại TU Kaiserslautern (Đức) và tiến sĩ tại Đại học Bách khoa Paris (Pháp).
Hiện TS Kỷ là thành viên chủ chốt của dự án Flyspeck, một trong những dự án lớn của toán học hình thức, nhằm xây dựng chứng minh được máy tính kiểm chứng cho giả thuyết Kepler – bài toán đã tồn tại gần 400 năm.
Trần Thu (tổng hợp)
