Giả thuyết thời gian hàm mũ bị chứng minh là sai? Một preprint gây tranh cãi từ OpenAI

Trong giới khoa học máy tính lý thuyết, có một giả thuyết đã đứng vững hơn hai thập kỷ và trở thành nền tảng cho hàng loạt kết quả nghiên cứu: Giả thuyết thời gian hàm mũ (Exponential Time Hypothesis – ETH). Nay, một preprint mới xuất hiện trên kho lưu trữ toán học của OpenAI tuyên bố thẳng thừng rằng giả thuyết này sai.

ETH là gì và tại sao nó quan trọng?

Vào năm 1999, các nhà nghiên cứu Russell Impagliazzo và Ramamohan Paturi đề xuất ETH như một giả định mạnh hơn phỏng đoán P ≠ NP quen thuộc. Cụ thể, ETH cho rằng bài toán 3-SAT không thể giải được trong thời gian dưới hàm mũ, tức không tồn tại thuật toán chạy trong khoảng O(2^(o(n))) cho mọi trường hợp.

Nghe có vẻ trừu tượng, nhưng ETH là "xương sống" của một lĩnh vực nghiên cứu mang tên độ phức tạp chính xác (fine-grained complexity). Hàng trăm công trình dựa vào giả thuyết này để chứng minh rằng nhiều bài toán thực tế — từ tìm đường đi ngắn nhất, so khớp chuỗi, đến các bài toán tối ưu trong học máy — không thể có thuật toán nhanh hơn một ngưỡng nhất định, trừ khi ETH bị bác bỏ.

Nói cách khác, nếu ETH sụp đổ, rất nhiều "giới hạn hiệu năng" mà giới nghiên cứu coi là tất yếu sẽ trở nên vô nghĩa.

Điều gì trong preprint mới?

Bài báo có tiêu đề "The Exponential Time Hypothesis is False" được đăng tải trong thư mục openai/math trên GitHub, thu hút sự chú ý trên Hacker News với 26 điểm và một số bình luận — con số không lớn, nhưng chủ đề thì đủ sức gây chấn động nếu được xác nhận.

Điểm đáng chú ý:

• Nguồn gốc bất thường: Đây là một preprint công bố trên repository GitHub của OpenAI, không phải trên arXiv hay tạp chí bình duyệt. Điều này khiến giới nghiên cứu đặt câu hỏi về mức độ kiểm chứng.
• Bản chất tuyên bố: Bác bỏ ETH đòi hỏi phải đưa ra một thuật toán giải 3-SAT nhanh hơn giới hạn hàm mũ — một kết quả mà nhiều chuyên gia cho là gần như không tưởng.
• Tính chưa được bình duyệt: Hiện chưa có thông tin về việc cộng đồng toán học và khoa học máy tính đã kiểm tra chéo (peer review) chứng minh hay chưa.

Góc nhìn cho độc giả Việt Nam

Với cộng đồng lập trình viên và sinh viên công nghệ thông tin tại Việt Nam, câu chuyện này mang hai bài học.

Thứ nhất, preprint không đồng nghĩa với chân lý. Trong toán học và khoa học máy tính lý thuyết, lịch sử đã ghi nhận không ít tuyên bố "phá vỡ giới hạn" sau đó bị phát hiện có lỗ hổng trong chứng minh — nổi tiếng nhất là các nỗ lực chứng minh P ≠ NP.

Thứ hai, sự kiện cho thấy các phòng thí nghiệm AI lớn đang mở rộng sang toán học thuần túy. Việc OpenAI duy trì một kho lưu trữ toán học riêng cho thấy tham vọng dùng AI để hỗ trợ nghiên cứu lý thuyết, một hướng đi mà nhiều trường đại học và viện nghiên cứu tại Việt Nam cũng đang quan tâm.

Cần theo dõi điều gì tiếp theo?

Giới chuyên môn sẽ tập trung vào ba câu hỏi:

• Liệu chứng minh có kiểm chứng được từng bước bằng các công cụ hỗ trợ chứng minh hình thức (như Lean, Coq) hay không?
• Cộng đồng fine-grained complexity phản ứng ra sao, khi hàng trăm kết quả dựa trên ETH có nguy cơ bị ảnh hưởng?
• Ai là tác giả thực sự đứng sau bài báo — con người, hay một hệ thống AI được huấn luyện để chứng minh định lý?

Trước khi có câu trả lời rõ ràng, thái độ hợp lý nhất là thận trọng chờ đợi. Nhưng dù kết quả cuối cùng ra sao, sự kiện này cũng là lời nhắc rằng trong khoa học máy tính, ranh giới giữa "không thể" và "chưa thể" luôn là nơi đáng để tranh luận.