OpenAI tuyên bố bác bỏ lý thuyết quan trọng "Giả thuyết thời gian mũ ETH" đã được sử dụng trong lĩnh vực khoa học máy tính hơn hai mươi năm

Tin tức BlockBeats, ngày 27 tháng 10, OpenAI mới đây đã tuyên bố rằng mô hình AI của họ đã "phá vỡ" ETH — thông tin này nhanh chóng gây ra tranh luận sôi nổi trong giới công nghệ và giới tiền mã hóa. Nhưng cần đặc biệt lưu ý rằng, ETH ở đây không phải là Ethereum (Ethereum) vốn được biết đến rộng rãi trong lĩnh vực tiền mã hóa, mà là một giả thuyết quan trọng đã tồn tại hơn hai mươi năm trong khoa học máy tính: Giả thuyết thời gian mũ (Exponential Time Hypothesis, gọi tắt là ETH).

Câu hỏi cốt lõi của giả thuyết thời gian mũ là: những bài toán trông có vẻ "đặc biệt khó tính" rốt cuộc khó đến mức nào?

Lấy ví dụ về "bài toán SAT" (bài toán thỏa mãn Boolean) mà một số người đã từng nghe đến, nó đặt câu hỏi: cho bạn một loạt điều kiện logic, liệu có thể tìm ra một cách gán giá trị để tất cả các điều kiện đồng thời được thỏa mãn? Khi quy mô bài toán trở nên lớn hơn, phương pháp tốt nhất hiện được biết về cơ bản chỉ có thể thử từng đáp án khả thi, chi phí thời gian sẽ tăng theo cấp số mũ khi quy mô tăng — tức là cái thường được gọi là "thời gian mũ". ETH tiếp tục khẳng định rằng, về bản chất loại bài toán này không thể được tăng tốc đáng kể, không tồn tại thuật toán hiệu quả theo nghĩa thực sự của "thời gian dưới mũ".

Giả thuyết này kể từ khi được đề xuất vào năm 1999, luôn là nền tảng quan trọng của khoa học máy tính lý thuyết. Hàng trăm hàng nghìn bài báo đều dựa trên nó để chứng minh "bài toán nào đó rất khó", "thuật toán nào đó đã gần tối ưu". Nếu ETH bị lật đổ, điều đó có nghĩa là nhiều bài toán mà chúng ta tưởng "gần như không thể nhanh hơn" có thể về mặt lý thuyết tồn tại cách giải tốt hơn.

OpenAI lần này tuyên bố rằng, mô hình của họ đã tìm ra một thuật toán tất định, có thể đếm chính xác số lượng nghiệm của bài toán k-SAT trong thời gian dưới mũ, và đã sử dụng Lean để xác minh hình thức. Nếu kết quả này cuối cùng chịu được sự kiểm tra của chuyên gia, nó sẽ trực tiếp làm lung lay giả thuyết thời gian mũ.