Hai lời giải cho một bài toán hơn 10 năm và câu chuyện đẹp phía sau
TS Vũ Khắc Kỷ và GS Trần Mạnh Tuấn vừa công bố một chứng minh hoàn chỉnh cho giả thuyết Courtade-Kumar, bài toán mở được đặt ra từ năm 2013. Điều đặc biệt là gần như cùng thời điểm, một nhóm nghiên cứu quốc tế có các nhà khoa học từ Google Research cũng công bố một lời giải độc lập bằng phương pháp khác.
Theo ông Vahab Mirrokni, Phó chủ tịch Google Research, giả thuyết Courtade-Kumar (CK) là một bài toán mở lâu năm ở giao điểm giữa lý thuyết thông tin và giải tích hàm Boolean. Trong một chuyên khảo, giả thuyết này được mô tả là một trong những bài toán mở quan trọng của lý thuyết thông tin.
Giả thuyết được đề xuất năm 2013, 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, nên chọn 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? Câu hỏi nghe có vẻ đơn giản, nhưng để chứng minh câu trả lời đúng trong mọi trường hợp lại là một bài toán rất khó.
Hai nhóm nghiên cứu độc lập vừa cùng đưa ra chứng minh cho giả thuyết này: Một công trình là Dictators are most informative của TS Vũ Khắc Kỷ, giảng viên Bộ môn Toán, Trường Đại học FPT, và GS Trần Mạnh Tuấn, Đại học Khoa học và Công nghệ Trung Quốc. Công trình còn lại do 7 nhà nghiên cứu đến từ Google Research, Chinese University of Hong Kong (CUHK) và các trường đại học khác thực hiện.
Hai nhóm đi theo những con đường khác nhau. Nhưng khi nhận ra họ đã độc lập đi đến cùng một kết quả, câu chuyện không trở thành cuộc đua xem ai xuất hiện trước. Nhóm của TS Kỷ và GS Trần Mạnh Tuấn đã chủ động lùi thời điểm công bố để hai lời giải được đưa ra gần như đồng thời. Theo TS Kỷ, đây là một cách để sự khác biệt chỉ vài giờ trên lịch không che khuất nhiều năm công sức của các nhà nghiên cứu ở cả hai phía.
Khi hai con đường khác nhau cùng đi tới một lời giải
Courtade-Kumar nằm ở giao điểm giữa lý thuyết thông tin và giải tích hàm Boolean. Có thể hình dung vấn đề một cách đơn giản: một chuỗi dữ liệu gồm nhiều bit được truyền qua một môi trường có nhiễu. Sau quá trình truyền, một số thông tin có thể bị thay đổi. Câu hỏi là nếu phải chọn ra một thông tin duy nhất từ dữ liệu ban đầu, nên chọn thế nào để người nhận vẫn có thể thu được nhiều thông tin nhất từ dữ liệu đã bị nhiễu?
Giả thuyết Courtade-Kumar dự đoán rằng cách tốt nhất là chọn trực tiếp một bit trong dữ liệu ban đầu. Trong toán học, loại hàm này được gọi là dictator function. Khó khăn nằm ở chỗ phải chứng minh điều đó đúng với một phạm vi rất rộng các hàm và điều kiện khác nhau.
Nhóm TS Kỷ và GS Trần Mạnh Tuấn đi theo hướng sử dụng entropy, giải tích và các công cụ liên quan đến cấu trúc phổ của hàm Boolean. Trong khi đó, nhóm nghiên cứu quốc tế sử dụng một cách tiếp cận dựa trên phương trình vi phân, kết hợp các tính toán và kiểm chứng hình thức.
Hai con đường khác nhau nhưng cùng dẫn đến một kết luận. Đây cũng là lý do hai công trình có giá trị tham khảo bổ sung cho nhau. Một lời giải không thay thế lời giải còn lại; cộng đồng toán học sẽ tiếp tục kiểm tra chi tiết các chứng minh và đánh giá những hệ quả mà mỗi phương pháp có thể mở ra.
Đáng chú ý, công trình của nhóm quốc tế còn sử dụng Lean, một hệ thống kiểm chứng hình thức, để kiểm tra các phần của chứng minh. Đây là cách tiếp cận ngày càng được quan tâm trong toán học, khi máy tính có thể hỗ trợ kiểm tra những lập luận phức tạp với độ chính xác rất cao.
Một email làm thay đổi câu chuyện về hai lời giải
Ít ai biết, phía sau hai công bố còn có một câu chuyện ít liên quan đến công thức nhưng đáng chú ý về cách các nhà nghiên cứu ứng xử với nhau. Trước khi công bố công trình, TS Kỷ chủ động gửi email cho GS Chandra Nair, người từng giới thiệu giả thuyết Courtade-Kumar với ông khoảng một thập kỷ trước, để thông báo rằng ông và GS Trần Mạnh Tuấn đã tìm được lời giải.
Phản hồi từ Hong Kong đem đến một bất ngờ: nhóm của GS Nair cùng các nhà nghiên cứu tại 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 Courtade-Kumar.
Hai bên trao đổi và xác nhận các kết quả được thực hiện độc lập. Khi đó, về nguyên tắc, mỗi nhóm đều có thể giữ nguyên lịch công bố của mình. Chênh lệch vài giờ hoàn toàn có thể tạo ra một câu chuyện về việc ai xuất hiện trước.
Nhưng hai nhóm đã chọn cách khác. Theo thông tin từ Trường Đại học FPT, nhóm của TS Kỷ và GS Trần Mạnh Tuấn chủ động lùi thời điểm công bố để hai kết quả được đưa ra gần như cùng lúc. Điều này không có nghĩa một bên từ bỏ đóng góp hay quyền được ghi nhận. Hai công trình vẫn độc lập, có tác giả và phương pháp riêng. Điều hai nhóm tránh đi là việc biến một khoảng cách rất nhỏ về thời gian thành thứ hạng tuyệt đối giữa hai kết quả được hình thành độc lập. Sau khi các công trình được công bố, hai nhóm tiếp tục trao đổi về những vấn đề nghiên cứu liên quan.
Câu chuyện Courtade-Kumar vì thế có hai lớp ý nghĩa. Ở lớp thứ nhất, một bài toán mở tồn tại hơn một thập kỷ đã có lời giải từ hai hướng tiếp cận khác nhau. Ở lớp thứ hai, phía sau những công thức và chứng minh là một cách ứng xử cho thấy cạnh tranh trong khoa học không nhất thiết phải biến thành đối đầu.
Một bài toán được đặt ra hơn một thập kỷ trước, một nhà nghiên cứu từng bỏ cuộc sau hai năm rồi quay lại, một cộng sự mới, hàng loạt lần thử sai và cuối cùng là hai nhóm độc lập cùng đi đến một kết luận.
Và thay vì để vài giờ công bố quyết định câu chuyện, họ chọn để hai lời giải và quá trình tạo ra chúng được nhìn nhận đúng với giá trị của mình.