KI-Beweis droht: Forscher beeilen sich mit Papier

Vào buổi sáng ngày 11 tháng Chín năm 2026, Dor Minzer nhận được tin nhắn của một người bạn. Bạn ông hỏi liệu ông có sắp giải được một câu hỏi cực kỳ nổi tiếng trong khoa học máy tính hay không. Minzer là giáo sư ở Học viện Công nghệ Massachusetts. Ông là chuyên gia về cái gọi là Giả thuyết Trò chơi Đơn nhất. Lúc đầu ông tưởng bạn đùa. Rồi tin nhắn tới dồn dập hơn. Tin đồn dần trở nên rõ ràng. Có khả năng công ty OpenAI đã tìm ra chứng minh cho Giả thuyết Trò chơi Đơn nhất. Ngay trước đó không lâu, OpenAI vừa công bố một chứng minh lớn về chất lỏng. Chứng minh này đang gây xôn xao khắp giới toán học. OpenAI có thể sẽ sớm công bố kết quả mới. Những tin nhắn gửi cho Minzer đều có chung một lời nhắn: nếu ông đã có kết quả riêng thì nên chia sẻ ngay đi.

Giả thuyết Trò chơi Đơn nhất là một câu hỏi rất nổi tiếng trong lý thuyết độ phức tạp. Lĩnh vực này chuyên tìm hiểu xem các bài toán là khó đến mức nào. Hiểu một cách đơn giản, vấn đề nằm ở chỗ này: ta phải đáp ứng rất nhiều quy tắc cùng một lúc. Việc đó có thể khó đến mức không tưởng. Ngay cả khi ta chỉ cần một lời giải tạm được chứ không cần lời giải tốt nhất thì vẫn rất khó. Nếu giả thuyết được chứng minh, nó cũng sẽ có ý nghĩa lớn với nhiều bài toán khác. Chứng minh đó tự động cho thấy: với nhiều bài toán khác, các phương pháp hiện nay không thể cải thiện thêm. Giới nghiên cứu sẽ tiến gần hơn tới một lý thuyết chung về sự khó khăn.

Minzer chưa chứng minh được Giả thuyết Trò chơi Đơn nhất. Nhưng ông cùng hai học trò là Yumou Fei và Shuo Wang đã chứng minh được một kết quả quan trọng cho một câu hỏi gần giống như vậy. Lúc đó họ vẫn đang viết bài. Bình thường, việc viết một bài báo như thế mất hàng tháng trời, thậm chí lâu hơn. Rồi tin đồn ập tới. Cả ba người dồn sức làm ngày làm đêm để hoàn thành bản thảo. Họ không muốn thông cáo báo chí của OpenAI lấn át công sức của mình. Ba ngày sau, họ đưa lên mạng một bài báo dài 95 trang. Với họ lúc đó, đầy đủ quan trọng hơn là rõ ràng, dễ đọc. Ngay trang đầu tiên, họ để lại một lời chú thích: “Bản hiện tại đã đầy đủ về mặt toán học, nhưng chưa phải là hình thức mà chúng tôi muốn chia sẻ.”

Dor Minzer cùng các học trò vội đưa một kết quả quan trọng lên mạng. Họ không muốn bị một chứng minh AI có thể xuất hiện lấn át.

Quyết định chạy đua của họ hóa ra hoàn toàn đúng. Vào ngày 6 tháng Mười, OpenAI thông báo đã chứng minh được Giả thuyết Trò chơi Đơn nhất. Cùng đợt đó, OpenAI còn thông báo thêm 376 kết quả khác thuộc nhiều lĩnh vực toán học. Trước loạt chứng minh bằng AI, giới nghiên cứu vừa lo lắng vừa tò mò. Tâm trạng này vốn rất bình thường sau mỗi bước tiến mới. Còn với kết quả của Minzer, phản ứng thuần nhất hơn nhiều.

Ryan O’Donnell là nhà khoa học máy tính ở Đại học Carnegie Mellon. Ông nhận xét: “Cậu ấy vốn đã có nhiều bài báo hay về chủ đề này. Và đây là một bài báo lớn nữa, thực sự rất đáng kể.”

Tạm ổn cũng đã tốt

Cả hai chủ đề đều xoay quanh việc phải chiều cùng lúc rất nhiều quy tắc. Các quy tắc này có thể mâu thuẫn với nhau. Ngoài đời cũng có những bài toán tương tự: như giải một ô Sudoku hay xếp chỗ ngồi cho tiệc cưới. Ai cũng muốn bạn bè được ngồi cùng nhau. Những vị khách không ưa nhau thì phải xếp khác bàn. Mà bàn nào cũng phải lấp đủ chỗ.

Giải chính xác những bài toán kiểu này có thể rất khó, thậm chí bất khả thi. Đôi khi vẫn có cách đáp ứng mọi quy tắc. Nhưng mọi cách làm đã biết đều chạy quá chậm. Hoặc các quy tắc vênh nhau đến mức không thể dung hòa. Khi đó sẽ chẳng có lời giải hoàn hảo nào cả.

Trong những trường hợp như vậy, giới nghiên cứu thường chấp nhận một lời giải gần đúng. Lời giải đó chỉ đáp ứng được một phần các quy tắc chứ không đáp ứng hết. Các nhà lý thuyết độ phức tạp muốn hiểu rõ: tại sao có lúc tìm lời giải kiểu này rất dễ, có lúc lại rất khó. O’Donnell nói: “Nhiều công trình đều cố tìm xem ranh giới nằm ở đâu.”

Giả thuyết Trò chơi Đơn nhất gắn chặt với hướng tìm kiếm đó. Nhà nghiên cứu Subhash Khot là người đầu tiên nêu nó trong một bài báo năm 2002. Hồi đó ông vẫn còn là sinh viên. Giả thuyết nói về một bài toán đặc biệt trên đồ thị. Đồ thị là mạng gồm các điểm nối với nhau bằng đường thẳng. Những đường thẳng đó gọi là cạnh. Ta nhận một đồ thị và phải tô màu các điểm. Số màu được cho trước và cố định. Mỗi cạnh đặt ra một quy tắc cho màu ở hai đầu của nó. Chẳng hạn, một cạnh yêu cầu hai điểm phải cùng màu. Một cạnh khác lại quy định: nếu một đầu màu đỏ thì đầu kia phải màu xanh dương. Và nếu một đầu màu xanh lá thì đầu kia phải màu vàng.

Subhash Khot đã nêu ra Giả thuyết Trò chơi Đơn nhất khi ông vẫn còn là sinh viên.