OpenAI công bố tuyên bố bác bỏ giả thuyết thời gian mũ, phát hiện ngày 16 và hình thức hóa bằng Lean ngày 17

OpenAI cho biết một mô hình AI nội bộ đã đưa ra thuật toán bác bỏ giả thuyết thời gian mũ (ETH) trong khoa học máy tính. Chữ viết tắt này trùng với mã của Ethereum(ETH), nhưng nghiên cứu không đưa ra cách phá hệ thống chữ ký hay tìm khóa riêng của ví tiền mã hóa.

Trong thông báo ngày 26, OpenAI cho biết mô hình nội bộ tìm ra kết quả bác bỏ vào ngày 16 và hình thức hóa chứng minh toán học bằng Lean vào ngày 17. Lean là công cụ dùng máy tính để kiểm tra chứng minh. Tài liệu nghiên cứu đã được công bố và đang được các chuyên gia bên ngoài đánh giá. Bài viết trước về kết quả bác bỏ giả thuyết và tài liệu hình thức hóa bằng Lean của OpenAI cũng đã đưa tin về nội dung này.

Giả thuyết thời gian mũ cho rằng khi số biến tăng, thời gian tính toán cần thiết để giải một số bài toán logic sẽ tăng rất nhanh. Một ví dụ tiêu biểu là 3-SAT, bài toán tìm xem có đáp án nào đồng thời thỏa mãn nhiều điều kiện đúng sai hay không. Trọng tâm nghiên cứu là liệu có thể tìm lời giải nhanh hơn về căn bản so với cách thử mọi tổ hợp điều kiện hay không.

Thuật toán OpenAI đưa ra xử lý một bài toán liên quan đến 3-SAT trong “thời gian gần mũ”. Điều này có nghĩa là khi kích thước bài toán tăng, thời gian tính toán tăng chậm hơn mức mà giả thuyết hiện hành đặt ra. Nếu nội dung bài báo là chính xác, các nghiên cứu dùng giả thuyết thời gian mũ để giải thích cận dưới độ khó tính toán của một số bài toán sẽ cần xem xét lại giả định đó.

OpenAI cho biết có hàng trăm bài báo dựa trên giả thuyết này trong các lĩnh vực như lý thuyết đồ thị, sinh học tính toán, cơ sở dữ liệu và hình học tính toán. Tuy nhiên, kết quả bác bỏ giả thuyết không khiến mọi kết luận trong các nghiên cứu trước đây mất hiệu lực. Một số nghiên cứu có thể dựa trên những giả định hoặc chứng minh khác.

Cần phân biệt việc bác bỏ giả thuyết thời gian mũ với khả năng giải mã tiền mã hóa trong thực tế. Kết quả lần này liên quan đến thời gian tính toán của các bài toán thuộc nhóm 3-SAT, không đưa ra cách tìm khóa riêng của ví Bitcoin(BTC) hay Ethereum hoặc phá hệ thống chữ ký. Cụm từ “thời gian gần mũ” cũng không có nghĩa là có thể nhanh chóng giải ngay những bài toán có kích thước thực tế.

Giáo sư MIT Ryan Williams (Ryan Williams), người phụ trách đánh giá, cho biết nếu kết quả được xác nhận là đúng thì các thuật toán nhanh hơn có thể xuất hiện cho những bài toán khác. Ông nói đã yêu cầu OpenAI xác minh trước liệu kết quả có ảnh hưởng đến các hệ thống mật mã hiện hành hay không và hiện chúng có vẻ vẫn an toàn. Đây là giải thích ban đầu, chưa phải kết luận cuối cùng của cuộc đánh giá độc lập. Phát biểu công khai của Ryan Williams

OpenAI cho biết cần nghiên cứu thêm để áp dụng tiến bộ lý thuyết này vào việc giải quyết các vấn đề thực tế. Cuộc đánh giá độc lập đang diễn ra sẽ xem xét liệu thuật toán và chứng minh được hình thức hóa có phù hợp với các tuyên bố trong bài báo hay không.