Giải thưởng Abel vinh danh sự kết hợp của toán học và khoa học máy tính

László Lovász (trái) và Avi Wigderson cùng nhận giải Abel 2021. Nguồn: Hungarian Academy of Sciences/Laszlo Mudra/AbelPrize; Cliff Moore/Institute for Advanced Study, Princeton/AbelPrizea

Hai nhà tiên phong của lý thuyết tính toán đã thắng giải Abel 2021, một trong những giải thưởng danh giá nhất của toán học.

Nhà toán học Hungary László Lovász và nhà khoa học máy tính Avi Wigderson sẽ cùng chia sẻ giải thưởng trị giá 7,5 triệu kroner Nauy (tương đương 886.600 USD) “cho những đóng góp mang tính nền tảng của họ cho lý thuyết khoa học máy tính và toán rời rạc, cũng như vai trò dẫn đầu của họ trong việc đưa những lĩnh vực này trở thành trung tâm của toán học hiện đại”, Viện Hàn lâm Khoa học Nauy cho biết như vậy trong một thông báo vào ngày 17/3/2021. 

Avi Wigderson, hiện làm việc tại Viện nghiên cứu Tiên tiến (IAS) ở Princeton, New Jersey, nói với Nature rằng giải thưởng này đã tôn vinh lý thuyết tính toán chứ không chỉ cho mỗi phần nghiên cứu của ông. “Tôi nghĩ nó vô cùng có ý nghĩa với lĩnh vực khoa học này”, ông nói.

“Ngày nay ngày càng khó khăn trong việc phân biệt toán học thuần túy và toán học ứng dụng – và tôi nghĩ đó là một điều tốt”, Lovász, hiện làm việc tại trường đại học Eötvös Loránd ở Budapest, nói.

Các thuật toán – vốn bao gồm những phương pháp đơn giản mà trẻ em học ở trường, như phép chia số dài – từng là trung tâm của toán học ít nhất là từ thời kỳ Hy Lạp cổ đại. Nhưng kể từ khi xuất hiện máy tính vào thế kỷ 20, tầm quan trọng trong nghiên cứu đã thay đổi từ câu hỏi “một thuật toán có thể giải quyết bài toán này không?” thành “ít nhất là về nguyên tắc, một thuật toán có thể giải quyết bài toán này trên một máy tính thông thường và trong một khoảng thời gian hợp lý không”?

Lovász và Wigderson đóng vai trò trung tâm trong những phát triển đó, Peter Sarnak, một nhà lý thuyết số tại IAS, nói. “Lý thuyết về tính phức hợp của các thuật toán và nghiên cứu về tốc độ giải các bài toán đã được phát triển trong những năm 1960 và 1970, và cả hai người họ đều chứng tỏ được rằng mình là những người đứng đầu”.

Từ toán học đến tính toán

Lovász sinh năm 1948 tại Budapest, lớn lên trong một môi trường mà những đứa trẻ tài năng được khuyến khích giải những bài toán khó. Paul Erdős, một trong những nhà toán học xuất sắc của kỷ nguyên hiện đại, đã truyền cảm hứng cho Lovász. Công việc nghiên cứu của Erdős tập trung vào toán học của các đối tượng rời rạc và sự liên hệ giữa chúng – ví dụ như các nút trong một mạng lưới – hơn là vào các biến liên tục vốn đặc trưng trong nhiều lĩnh vực như hình học, nhà toán học Péter Pál Pálfy tại Viện nghiên cứu toán học Alfréd Rényi ở Budapest nói.

Lovász bắt đầu sự nghiệp tại thời điểm khi các chủ đề trong toán rời rạc như lý thuyết mạng lưới – từng bị các nhà toán học “thuần túy” coi thường – trở nên quan trọng cả trong các lĩnh vực khác của toán học và ứng dụng như phân tích dữ liệu lớn. Ông quan tâm đến nghiên cứu cơ bản cũng như những ứng dụng của nó, và làm việc toàn thời gian cho Microsoft trong vòng bảy năm khi giữ các vị trí nghiên cứu học thuật. Ông đã giải quyết những bài toán lớn về lý thuyết toán học của mạng lưới như tính toán số các cách có thể để tô màu các điểm nút mà vẫn đảm bảo cho hai điểm cạnh nhau luôn luôn có màu sắc khác nhau.

Một trong những kết quả xuất sắc nhất của Lovász là một thuật toán mà ông tạo ra cùng với hai nhà lý thuyết số Hà Lan, hai anh em Arjen và Hendrik Lenstra. Thuật toán mang tên LLL này đã chia một vectơ lớn được tạo ra từ những số nguyên thành tổng của những vectơ ngắn nhất có thể của dạng này. Nó có nhiều ứng dụng trong nhiều lĩnh vực của toán học thuần túy và trở thành cốt lõi với nghiên cứu về mã hóa dữ liệu. Các khóa mật mã được thiết lập trên cơ sở các vertor nguyên được xem là có nhiều hứa hẹn cho an ninh mạng tương lai bởi vì không giống như những khóa mật mã thường được sử dụng trong truyền thông hiện nay, nó được cho là không dễ bị phá bởi các máy tính lượng tử.

 Lovász là chủ tịch Hội toán học quốc tế từ năm 2007 đến 2010. Ông cũng là chủ tịch Viện Hàn lâm KH Hungary từ năm 2014 đến 2020, và trong suốt những năm đó đã đi đầu trong một nỗ lực táo bạo nhưng cuối cùng thất bại - nỗ lực ngăn cản chính phủ Hungary tiếp quản các viện nghiên cứu của Viện hàn lâm. Ông và nhiều nhà khoa học khác cho rằng điều này có thể làm giảm tính độc lập của các nhà nghiên cứu.

Từ tính toán đến toán học

Wigderson sinh ra tại Haifa, Israel năm 1956. Ông nghiên cứu tại Israel và Mỹ và làm việc tại nhiều cơ sở nghiên cứu trước khi chuyển tới IAS vào năm 1999, nơi ông làm việc từ đó đến nay. Giải Abel mà ông nhận được ghi nhận đóng góp của ông cho nhiều lĩnh vực thực tiễn của khoa học máy tính, trong đó ông “tấn công” vào bất kỳ bài toán nào với các công cụ toán học bất kỳ mà ông tìm thấy, ngay cả công cụ từ các lĩnh vực xa xôi. Đam mê của Wigderson cho lĩnh vực nghiên cứu của mình rất dễ “lây nhiễm” cho người khác, Sarnak nói. “Khi ông ấy nói với anh, anh hoàn toàn cảm thấy là ‘Chúa ơi, tốt hơn là mình nên gac lại những gì mình đang làm và bắt đầu tìm hiểu về điều đó’”.

Một trong những thành công nổi tiếng bậc nhất của Wigderson là sự phân loại vai trò của ngẫu nhiên trong tính toán. Trong nhiều trường hợp, như tìm kiếm đường thoát khỏi một mê cung, thì việc tung một đồng xu ngẫu nhiên cũng có thể là một thuật toán giúp tìm ra đường nhanh chóng, mặc dù các lý do vì sao tìm được thì lại không rõ ràng. “Rất nhiều chương trình chạy nhanh hơn nếu như anh cho phép chúng thực hiện sự lựa chọn ngẫu nhiên đó”, Sarnak nói.

Cùng với những cộng sự trong những năm 1990, Wigderson chứng tỏ là nếu việc sử dụng một thuật toán ngẫu nhiên dường như đạt hiệu quả thì phải tồn tại một thuật toán phi ngẫu nhiên gần như hiệu quả. Điều này đem lại một sự cam đoan về mặt lý thuyết  rằng các thuật toán ngẫu nhiên thực sự tìm được các giải pháp đúng.

 Một công trình lớn khác của Wigderson đang ngày một trở nên phù hợp với nền kinh tế thông tin. Nó bao hàm giao thức phi kiến thức, một cách cho phép người ta xác nhận được sự đúng đắn của một tuyên bố mà không cần tiết lộ bất kỳ thông tin nào về những gì tuyên bố đó nói ra.

Giao thức phi kiến thức là trung tâm trong những loại tiền số như Bitcoin, và có thể giúp xác định được danh tính của một cá nhân. Bằng việc trả lời những câu hỏi của người thẩm tra, người ta có thể đưa ra một giao thức phi kiến thức có mật khẩu chính xác, ví dụ như vậy, mà không cần tiết lộ chính mật khẩu đó. Wigderson và cộng sự đã chứng minh vào năm 1991 là tất cả những tuyên bố toán học về bản chất có thể được diễn dịch theo một cách cho phép một giao thức phi kiến thức – có thể là điều gây ngạc nhiên nhất, nghịch lý nhất” của những kết quả nghiên cứu, Wigderson nói.

Kể từ khi thành lập giải Abel vào năm 2003, Lovász là người Hungary thứ ba và Wigderson là người Israel thứ nhì thắng giải. Với ngoại lệ của Karen Keskylla Uhlenbeck vào năm 2019, mọi người thắng giải này đều là nam.

Thanh Phương tổng hợp

TS. Nguyễn Quang (ĐH Duy Tân) hiệu đính

Nguồn: https://www.nature.com/articles/d41586-021-00694-9; https://www.abelprize.no/