OpenAI và Anthropic tuyên bố AI bác bỏ giả thuyết thời gian mũ tồn tại 25 năm

Ngày 26 tháng 10, OpenAI và Anthropic tuyên bố các mô hình AI của họ đã tìm ra thuật toán giải bài toán 3-SAT nhanh hơn thời gian mũ, qua đó bác bỏ Giả thuyết Thời gian Mũ (ETH). Hai công ty đã công bố bài nghiên cứu và chứng minh hình thức.

ETH cho rằng khi quy mô đầu vào của một số bài toán tính toán tăng lên, thời gian cần để giải cũng tăng theo hàm mũ. Giả thuyết này được đề xuất cách đây khoảng 25 năm và là tiền đề trong nghiên cứu khoa học máy tính lẫn sinh học.

3-SAT là bài toán xác định liệu có đáp án thỏa mãn đồng thời nhiều điều kiện logic hay không. Cụ thể, ETH cho rằng không tồn tại thuật toán tất định giải 3-SAT trong thời gian 2^{o(n)} ở trường hợp xấu nhất, với n là số biến.

Bài nghiên cứu OpenAI công bố đưa ra thuật toán tất định đếm chính xác số nghiệm của các công thức logic k-CNF. Bản thảo được soạn ngày 17 tháng 10, còn bản sửa đổi công bố ngày 25 tháng 10. Phần tác giả chỉ ghi OpenAI.

Anthropic cho biết mô hình Claude dùng trong nghiên cứu nội bộ đã tìm ra thuật toán giải 3-SAT trong phạm vi tính toán lý thuyết với thời gian ngắn hơn thời gian mũ. Công ty công bố bài nghiên cứu do Claude viết cùng chứng minh hình thức Lean 4.

Cả hai công ty đều nêu rõ giới hạn của kết quả. Anthropic nói nghiên cứu xem xét lượng tính toán khi quy mô bài toán trở nên rất lớn, nên không có nghĩa thuật toán sẽ giải nhanh các bài toán thực tế. OpenAI cũng viết trong bài nghiên cứu rằng kết quả không đồng nghĩa mọi bài toán NP đều có thuật toán nhanh hơn thời gian mũ.

Lean là công cụ cho phép máy tính kiểm tra các chứng minh đã được hình thức hóa. Việc hai công ty công bố tài liệu Lean giúp kiểm tra được chứng minh, nhưng tự nó chưa đồng nghĩa giới nghiên cứu đã hoàn tất đánh giá độc lập.

Vài ngày sau thông báo, Russell Impagliazzo và Ramamohan Paturi, những người đề xuất ETH, cùng Ryan Williams, nhà nghiên cứu tại Viện Công nghệ Massachusetts, trả lời phỏng vấn AFP về ý nghĩa của kết quả, việc đánh giá độc lập và vai trò còn lại của con người.

Impagliazzo nói: “Sẽ tốt hơn nhiều nếu một con người có thể phát hiện ra điều này và giải thích quá trình suy nghĩ.” Ông nói con người có thể giải thích cả con đường đi đến đáp án, và đôi khi quá trình ấy cũng quan trọng như chính đáp án.

Paturi cho biết phản ứng đầu tiên của ông là ngạc nhiên. Ông nói những thành quả nghiên cứu trong 30 năm qua dựa trên giả thuyết này không biến mất chỉ vì kết quả mới được công bố.

Williams nói: “Tôi chưa bao giờ hoàn toàn tin vào giả thuyết này.” Ông từng công khai nghi vấn về ETH và cho rằng kết quả lần này củng cố sự hoài nghi của mình.

Ba nhà nghiên cứu đang tham gia tổ chức một cuộc đánh giá độc lập đối với tuyên bố của hai công ty. OpenAI cũng cho biết nhóm nghiên cứu bên ngoài do Impagliazzo, Paturi và Williams dẫn dắt dự kiến xem xét chứng minh.

Paturi nói con người vẫn giữ vai trò mở rộng ranh giới nghiên cứu, định hướng và phát triển lĩnh vực. Ông khuyên sinh viên học cách sử dụng những công cụ này đồng thời rèn luyện khả năng phán đoán. Williams nói lĩnh vực đang trải qua thay đổi lớn, nhưng nghiên cứu vẫn đáng để theo đuổi.

Impagliazzo bày tỏ lo ngại rằng trong nghiên cứu, AI có thể đảm nhận việc giải bài toán còn con người phụ trách kiểm chứng và giải thích. Theo ông, vai trò đó có thể còn thuộc về các nhà nghiên cứu cho đến khi AI phát triển hơn nữa.

Paturi cảnh báo nếu quyền tiếp cận các công cụ nghiên cứu mạnh tập trung vào doanh nghiệp, cần xem xét ai được tham gia nghiên cứu, ai được dùng công cụ trước và ai quyết định chủ đề nghiên cứu. Ông nói: “Thông báo của doanh nghiệp không thể thay thế bình duyệt.”

ETH cũng là chữ viết tắt trùng với mã của Ethereum (ETH), nhưng hai thuật ngữ chỉ trùng ký tự; nghiên cứu này không liên quan đến Ethereum.

Impagliazzo nói bản thân kết quả hiện tại không phải là mối đe dọa đối với an ninh thông tin. Ông cho rằng nghiên cứu trong tương lai có thể khiến nhu cầu về mã hóa mạnh hơn tăng lên, nhưng nhấn mạnh điều đó không có nghĩa các hệ thống mã hóa hiện nay đã bị phá vỡ.