AI lật đổ giả thuyết 27 năm tuổi: Khi hàng loạt nghiên cứu khoa học máy tính bỗng trở nên 'vô nghĩa'

Tuần này, cả OpenAI lẫn Anthropic đều tuyên bố đã bác bỏ giả thuyết thời gian lũy thừa (Exponential Time Hypothesis – ETH), một trụ cột của khoa học máy tính lý thuyết suốt 27 năm qua. Nếu kết quả này được xác nhận, hàng loạt công trình nghiên cứu về độ phức tạp thuật toán sẽ phải viết lại từ đầu.

Cú sốc với giới nghiên cứu lý thuyết

ETH đặt nền móng cho giả định rằng khi bài toán càng lớn, thời gian để giải nó sẽ tăng theo cấp số nhân. Gần như toàn bộ nghiên cứu về thiết kế thuật toán và độ phức tạp tính toán trong nhiều thập kỷ đều dựa trên tiền đề này.

Giáo sư Peter Jonsson tại Đại học Linköping (Thụy Điển) chuẩn bị trình bày công trình của mình tại Hội nghị IEEE về Nền tảng Khoa học Máy tính – một trong những hội nghị danh giá nhất ngành – thì nhận tin dữ. Theo ông, phần lớn công trình đó giờ đã "chết".

"Người ta sẽ mở đầu bài thuyết trình kiểu: 'ETH sai rồi, một nửa bài báo của tôi không còn giá trị'. Thật đau đầu, nhưng đồng thời chúng ta cũng học được rất nhiều. Khoa học là vậy."

Giới nghiên cứu chưa có thời gian kiểm chứng độc lập, chứ chưa nói đến việc hiểu thấu đáo các chứng minh do AI tạo ra. Cả hai công ty đã công bố chứng minh trên GitHub dưới dạng ngôn ngữ tự nhiên và định dạng Lean (có thể kiểm tra bằng máy). OpenAI đã mời các nhà khoa học máy tính tại Đại học California, Santa Barbara – những người đề xuất giả thuyết ban đầu – cùng một học giả MIT từng bác bỏ một phiên bản của ETH, đứng ra tập hợp cộng đồng giải mã chứng minh. Hiện nhóm này mới dừng ở một biểu mẫu Google kêu gọi tình nguyện viên và cam kết tài trợ một hội nghị về chủ đề này.

"Một quả bom khổng lồ thả giữa ngành"

Giáo sư Daniel Lokshtanov (UC Santa Barbara) ước tính nếu kết quả được xác nhận, ông sẽ "sai một cách thiên hà" và khoảng 50 bài báo đã công bố của ông sẽ trở nên vô nghĩa hoặc phải xem xét lại.

"Nó giống như một quả bom khổng lồ thả giữa ngành. Vừa tuyệt vời vừa khủng khiếp."

Thore Husfeldt, trưởng nhóm nghiên cứu thuật toán tại Đại học IT Copenhagen, cho biết ông dành gần cả năm trời cho một bài toán duy nhất trong lĩnh vực của mình, và giờ "tất cả đều không còn liên quan". Chính ông từng đưa ra một phiên bản của giả thuyết nay bị OpenAI bác bỏ.

Khác với tâm trạng ảm đạm của giới toán học khi đối mặt với các chứng minh do AI tạo ra, Husfeldt lại tỏ ra hào hứng:

"Làm toán giống như mò mẫm trong một căn phòng tối om. Bỗng nhiên có ai đó rọi đèn pha khắp cả một lĩnh vực con, và giờ chúng tôi chạy nhốn nháo như những chú thỏ phấn khích, nhìn ngắm mọi ngóc ngách mà trước đây không thể chạm tới."

Áp lực tâm lý và làn sóng "rác" học thuật

Tuy vậy, ông cũng thừa nhận áp lực tâm lý không hề nhỏ. Vài tháng gần đây, cứ mỗi tuần hoặc hai tuần, các kết quả do AI công bố lại "xóa sổ" công trình của nhiều người. Khoa của ông thậm chí đã tính đến việc thuê chuyên gia tâm lý lao động, bởi "có những người thực sự trầm cảm và buồn bã".

Bên cạnh đó là vấn đề khối lượng nội dung khổng lồ do AI tạo ra. Trong lúc phỏng vấn, Husfeldt nhận được một bài báo 17 trang nghi do AI viết về hệ quả của kết quả ETH, gửi từ một địa chỉ Gmail lạ. Ông từ chối đọc:

"Đọc toán là một khoản đầu tư trí tuệ rất lớn."

Đầu tháng này, OpenAI từng tung lên GitHub 722 bản thảo về 400 bài toán, khiến giới học thuật bức xúc vì khó tiêu hóa. Một số tài liệu còn chứa lỗi, khiến nhiều nhà toán học cho rằng công ty vội vã công bố để làm đẹp hồ sơ trước thềm IPO. Lần này, bài báo khoảng 60 trang về ETH được đánh giá là viết tốt hơn các ấn phẩm trước đó.

Hệ quả với mật mã học và cơ hội mới

Nếu ETH sai – tức là không nhất thiết phải mất thời gian tăng theo cấp số nhân để giải các bài toán phức tạp – thì đây là tin "đáng mừng", theo phó giáo sư Victor Lagerkvist (Linköping). Ông dự định quay lại những bài toán từng phải bỏ dở vì tin rằng ETH đúng.

Kết quả này cũng có thể ảnh hưởng đến mật mã học đứng sau bảo mật web, vốn dựa trên giả định rằng một số bài toán nhất định mất thời gian dài đến mức không thực tế để giải. Dù kết quả cụ thể này chưa tác động trực tiếp đến mật mã, Lokshtanov cảnh báo: "Nó chắc chắn sẽ khiến một số nhà thiết kế hệ thống mật mã lo lắng."

Husfeldt nhấn mạnh tầm quan trọng của việc tiếp tục nghiên cứu lý thuyết, có sự hỗ trợ của AI:

"Chúng ta muốn quy trình khoa học mở chỉ ra những hiểu lầm về tính toán, đặc biệt vì phần lớn hạ tầng số hiện đại được xây trên các giả định về tính toán."

Với Jonsson, ông dự định xem lại các bài báo của mình và của đồng nghiệp vốn dựa trên ETH, và tin rằng bài hội nghị của ông có thể cứu được bằng phương pháp khác:

"Tôi không quan tâm chứng minh đó do người viết, do AI viết, hay do người ngoài hành tinh truyền đến. Nếu nó đúng, chúng ta phải dùng nó cho tương lai."