Giả thuyết Courtade-Kumar: bài toán mở ở giao điểm lý thuyết thông tin và hàm Boolean
Giả thuyết Courtade-Kumar, còn gọi là "Most Informative Boolean Function Conjecture", là một bài toán mở trung tâm nằm ở giao điểm giữa lý thuyết thông tin và phân tích hàm Boolean, đặt câu hỏi dữ liệu nên được mã hoá và chọn lọc thế nào qua kênh nhiễu để tối đa hoá lượng thông tin được giữ lại ở đầu ra, và khẳng định rằng chiến lược tối ưu không phải là những quy tắc phức tạp mà là dùng một hàm kiểu “độc tài” chỉ nhìn vào một bit đầu vào thay vì kết hợp nhiều bit với cấu trúc rối rắm.
Trong ngôn ngữ của lý thuyết thông tin, bài toán xuất phát từ câu hỏi: khi dữ liệu truyền qua kênh nhiễu, ta nên chọn và xử lý thông tin ban đầu thế nào để tối đa hoá lượng thông tin ở đầu ra. Điều gây bất ngờ là giả thuyết Courtade-Kumar dự đoán lời giải cực kỳ “đơn giản”: 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. Đằng sau vẻ giản dị đó là cấu trúc sâu về entropy, thông tin tương hỗ và toán tử nhiễu trên không gian Boolean, kết nối tới nhiều bài toán tối ưu hoá và bất đẳng thức quan trọng trong toán học.
Cột mốc: hai nhà khoa học Việt Nam công bố chứng minh hoàn chỉnh
Ngày 21/9, bài báo "Dictators are most informative" của TS. Vũ Khắc Kỳ (ĐH FPT) và PGS. Trần Mạnh Tuấn (ĐH Khoa học và Công nghệ Trung Quốc) được đăng trên kho tiền ấn phẩm khoa học arXiv, công bố chứng minh hoàn chỉnh giả thuyết Courtade-Kumar. Đây không phải là một kết quả “vá víu” thêm một trường hợp riêng lẻ, mà là chứng minh toán học cho toàn bộ lớp hàm Boolean, bao gồm cả các hàm mất cân bằng, vốn là phần khó nhất của bài toán.
Đáng chú ý, gần như đồng thời, một nhóm gồm các nhà khoa học từ Google và nhiều trường đại học trên thế giới cũng công bố một chứng minh độc lập cho cùng giả thuyết. Phó Chủ tịch Google Research Vahab Mirrokni đã thông báo kết quả của nhóm ông và gửi lời chúc mừng tới hai nhà khoa học Việt Nam, đồng thời gọi Courtade-Kumar là "một bài toán mở trung tâm lâu năm tại giao điểm của lý thuyết thông tin và phân tích Boolean" và "một trong những bài toán mở quan trọng nhất của lý thuyết thông tin". Sự công nhận công khai này là một trích dẫn hiếm thấy dành cho công trình đến từ Việt Nam trong một vấn đề nền tảng của toán học và khoa học máy tính.
Hơn một thập kỷ kiên trì và cuộc "hôn phối" của hai cách nhìn toán học
Hành trình dẫn tới lời giải bắt đầu khoảng mười năm trước, khi TS. Vũ Khắc Kỳ làm nghiên cứu sau tiến sĩ tại Đại học Trung Quốc Hồng Kông, được giới thiệu về giả thuyết Courtade-Kumar bởi GS. Chandra Nair và theo đuổi bài toán trong khoảng hai năm nhưng chưa tìm được đột phá. Sau khi trở về Việt Nam giảng dạy từ tháng 1/2019, ông vẫn thỉnh thoảng quay lại bài toán, song mọi phương pháp thử nghiệm đều vấp phải những trở ngại mà cộng đồng toán học đã nhận diện.
Bước ngoặt xuất hiện năm 2025, khi ông đi sâu vào hướng hình học thông tin, tìm cách dùng công cụ hình học để giải các bài toán trong học máy. Từ cách nhìn này, ông nhận ra giả thuyết Courtade-Kumar mang nhiều cấu trúc liên quan đến entropy, thông tin tương hỗ và biến đổi thông tin dưới tác động của nhiễu. Việc cộng tác với PGS. Trần Mạnh Tuấn, chuyên gia hàng đầu về xác suất rời rạc và tổ hợp, tạo ra một "cuộc hôn phối" thú vị: công cụ tổ hợp, xác suất và cấu trúc rời rạc của PGS. Tuấn bổ sung cho hướng entropy và giải tích mà TS. Kỳ đang theo, cho phép họ liên tục thử nghiệm, loại bỏ, hoàn thiện ý tưởng. Qua đó, họ xây dựng được cấu trúc chứng minh kết hợp ước lượng entropy, phổ Fourier của hàm Boolean và một số bất đẳng thức tô màu, rồi mở rộng dần cho tới trường hợp tổng quát, gồm cả hàm mất cân bằng.
Ý nghĩa khoa học: từ lời giải cho một giả thuyết đến hướng nghiên cứu mới
Việc chứng minh giả thuyết Courtade-Kumar không chỉ giúp cộng đồng toán học "đóng" lại một bài toán mở kéo dài hơn một thập kỷ, mà còn gửi đi một thông điệp quan trọng về cách ta hiểu thông tin và nhiễu. Giả thuyết khẳng định rằng những hàm kiểu “độc tài” – chỉ dựa vào một bit đầu vào – là các hàm thông tin nhất trong bối cảnh kênh nhiễu hai giá trị, phá vỡ trực giác phổ biến rằng cần những quy tắc phức tạp mới giữ lại được nhiều thông tin. Khi lời khẳng định này trở thành định lý, nó ép giới nghiên cứu phải xem xét lại cách họ thiết kế và phân tích hệ thống xử lý tín hiệu, mã hoá dữ liệu, cũng như các mô hình học máy trong môi trường có nhiễu.
Không kém phần quan trọng là "hộp công cụ" toán học được tạo ra trong quá trình chứng minh. Công trình của hai nhà khoa học Việt Nam cho thấy các bất đẳng thức entropy, cấu trúc toán tử nhiễu trên không gian Boolean và những kỹ thuật về phổ Fourier có thể phối hợp để phá giải một bài toán vốn được xem là rất khó. Theo chính các tác giả, những công cụ này có thể mở ra khả năng áp dụng vào các bài toán khác trong lý thuyết thông tin, phân tích Boolean và tối ưu hoá, thay vì dừng lại ở một chiến thắng đơn lẻ cho giả thuyết Courtade-Kumar. Đáng chú ý, trí tuệ nhân tạo cũng được dùng để kiểm tra giả thuyết phụ và tìm phản ví dụ, giúp họ sớm loại bỏ các hướng đi kém hiệu quả, nhưng AI không thay thế vai trò sáng tạo của nhà toán học.
Thông điệp cho khoa học cơ bản: người Việt có thể giải bài toán trung tâm của thế giới
Trên bình diện khoa học, sự kiện này là một lời khẳng định thẳng thắn rằng các nhà khoa học Việt Nam hoàn toàn có thể tham gia trực tiếp vào việc giải quyết những bài toán nền tảng mang tầm quốc tế, nếu có hướng tiếp cận đúng và đủ thời gian kiên trì với các câu hỏi khó. Khi một bài toán được Phó Chủ tịch Google Research mô tả là "bài toán mở trung tâm lâu năm" của lý thuyết thông tin được giải bởi một nhóm tác giả trong đó có giảng viên toán học làm việc tại Việt Nam, hình ảnh nghiên cứu khoa học cơ bản của Việt Nam được đặt trước một tấm gương mới: không chỉ theo sau, mà có thể đi song song với các trung tâm khoa học lớn.
Mỗi cách chứng minh – của nhóm Việt Nam và nhóm quốc tế – có thế mạnh riêng và sẽ cần thời gian để cộng đồng đánh giá. Nhưng bất luận kết quả so sánh thế nào, việc hai lời giải độc lập xuất hiện gần như cùng lúc cho thấy giả thuyết Courtade-Kumar đã chín muồi và lĩnh vực lý thuyết thông tin đang bước sang một giai đoạn mới. Từ nay, câu hỏi không còn là "giả thuyết đúng hay sai", mà là "ta có thể dùng những ý tưởng từ các chứng minh này để tiến xa hơn đến đâu". Trong bức tranh đó, câu chuyện TS. Vũ Khắc Kỳ và PGS. Trần Mạnh Tuấn kiên trì hơn một thập kỷ với một bài toán khó sẽ là một ví dụ mạnh mẽ cho các thế hệ trẻ về giá trị lâu dài của nghiên cứu khoa học cơ bản.
