OpenAI tuyên bố đã bác bỏ Giả thuyết Thời gian Mũ bằng thuật toán mới

ChainCatcher đưa tin, gần đây OpenAI thông báo rằng mô hình AI của họ đã phá vỡ giả thuyết thời gian mũ, một giả thuyết đã được sử dụng trong khoa học máy tính suốt hơn hai mươi năm, viết tắt bằng tiếng Anh là ETH, không phải Ethereum. Giả thuyết này tập trung vào mức độ khó của các bài toán cực kỳ phức tạp, lấy ví dụ về bài toán khả năng thỏa mãn Boolean (SAT): cho một tập hợp các điều kiện logic, liệu có tồn tại một cách gán giá trị sao cho tất cả các điều kiện cùng đúng không? Khi quy mô bài toán tăng lên, phương pháp tốt nhất được biết đến hiện nay gần như chỉ có thể thử từng đáp án có thể, và chi phí thời gian tăng theo hàm mũ với quy mô. Giả thuyết thời gian mũ còn khẳng định rằng các bài toán loại này về bản chất không thể được tăng tốc đáng kể, và không tồn tại thuật toán hiệu quả thực sự nào chạy trong thời gian dưới mũ. Kể từ khi được đề xuất năm 1999, giả thuyết này đã trở thành nền tảng quan trọng trong khoa học máy tính lý thuyết, với hàng ngàn bài báo dựa vào nó để chứng minh rằng một số bài toán là khó, hoặc một số thuật toán đã gần như tối ưu. Nếu giả thuyết thời gian mũ bị bác bỏ, điều đó có nghĩa là nhiều bài toán được cho là gần như không thể giải nhanh hơn về mặt lý thuyết có thể tồn tại cách giải tốt hơn. OpenAI tuyên bố rằng mô hình của họ đã tìm ra một thuật toán xác đị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à đã được xác minh hình thức bằng Lean. Nếu kết quả này cuối cùng vượt qua được sự kiểm tra của các chuyên gia, nó sẽ trực tiếp làm lung lay giả thuyết thời gian mũ.