OpenAI ngày 27/10 (giờ địa phương) cho biết mô hình AI của hãng đã tìm ra một thuật toán mới trong lý thuyết tính toán, được cho là có thể thách thức Exponential Time Hypothesis (ETH). Tuy vậy, kết quả này hiện vẫn cần được giới toán học kiểm chứng độc lập, đồng thời phải qua thêm nhiều nghiên cứu để xác định liệu nó có thể chuyển hóa thành cải thiện hiệu năng tính toán trong thực tế hay không.

Theo Decrypt, trong một bài báo dài 67 trang, OpenAI trình bày một thuật toán tất định có thể giải bài toán 3-SAT nhanh hơn so với những gì giới nghiên cứu từng dự đoán. ETH là giả thuyết cho rằng không tồn tại thuật toán có thể giải một số bài toán nhanh hơn đáng kể so với thời gian hàm mũ. Kể từ khi được đưa ra năm 1999, giả thuyết này đã trở thành nền tảng quan trọng trong nhiều lĩnh vực, từ lý thuyết đồ thị đến sinh học tính toán.

Thông tin trên cũng gây xôn xao trong cộng đồng tiền mã hóa do chữ viết tắt ETH trùng với mã giao dịch của Ethereum. Trên X, một số người dùng đăng tải các bình luận mang tính đùa cợt, cho rằng “các trader thuật toán đã đánh sập Ethereum” hoặc nhắc đến việc Vitalik Buterin “im lặng” sau thông tin này. Tuy nhiên, ETH trong nghiên cứu của OpenAI là Exponential Time Hypothesis, không liên quan đến Ethereum.

Trọng tâm của nghiên cứu là thuật toán đếm số nghiệm của bài toán 3-SAT. Đây là một bài toán kinh điển, yêu cầu tìm tổ hợp biến có thể đồng thời thỏa mãn nhiều điều kiện logic. OpenAI cho biết đã đưa ra phương pháp đếm số nghiệm trong thời gian dưới mức hàm mũ theo số lượng biến. Nếu kết quả này được xác nhận, cách nhìn về nhiều bài toán tính toán liên quan có thể thay đổi đáng kể.

OpenAI cho biết mô hình AI đã tìm ra kết quả trên vào ngày 16/10. Đến ngày hôm sau, công ty đã hình thức hóa chứng minh này bằng Lean, phần mềm kiểm chứng chứng minh toán học theo phương pháp hình thức. Tài liệu liên quan cũng đã được công bố trên GitHub.

Dù vậy, giới toán học vẫn tỏ ra thận trọng. Trong thư ngỏ, Russell Impagliazzo, Ramamohan Paturi và Ryan Williams của MIT cho biết việc tham gia rà soát không đồng nghĩa với việc xác nhận kết quả, đồng thời kêu gọi tiếp tục tái lập và kiểm tra độc lập.

Anthropic cũng công bố một bài báo liên quan đến thuật toán cho 3-SAT vào ngày 26/10 dưới tên Claude. Tuy nhiên, công ty lưu ý rằng kết quả này chỉ phản ánh cải thiện về độ phức tạp thời gian ở cấp độ lý thuyết, chưa liên hệ trực tiếp đến hiệu năng giải bài toán trong thực tế.

OpenAI cũng thừa nhận vẫn cần thêm nhiều nghiên cứu để biến tiến bộ về mặt lý thuyết thành cải thiện hiệu năng thực tế. Công bố lần này không đồng nghĩa với việc mọi bài toán trong lớp NP đều có thể được giải nhanh, và bài toán P so với NP vẫn chưa có lời giải. Dù vậy, nghiên cứu tiếp tục cho thấy tiềm năng của AI trong khám phá toán học, ngay cả khi ý nghĩa đầy đủ của kết quả vẫn phải chờ thêm các bước kiểm chứng độc lập.