AI bác bỏ Giả thuyết Thời gian Lũy thừa: Ý nghĩa của tất cả điều này

OpenAI và Anthropic mỗi bên đã công bố một chứng minh rằng giả thuyết thời gian lũy thừa là sai.

ETH là một giả định đã tồn tại 27 năm trong khoa học máy tính lý thuyết, cho rằng một số bài toán không bao giờ có thể được giải nhanh hơn nhiều so với vét cạn. Giờ đây, các phòng thí nghiệm AI hàng đầu nói rằng điều đó đơn giản là không đúng.

Nếu các chứng minh đứng vững, đây là kết quả do AI tạo ra quan trọng nhất trong khoa học máy tính cho đến nay. Chúng cũng buộc phải xem xét lại hàng trăm bài báo nghiên cứu vốn giả định ETH là đúng.

Trong bài viết này, chúng tôi giải thích giả thuyết thời gian lũy thừa thực sự có nghĩa là gì, cùng với P so với NP, vốn có liên quan. Chúng tôi cũng sẽ xem chính xác hai phòng thí nghiệm đã tuyên bố gì, cách kiểm chứng các chứng minh, và điều gì thay đổi (và không thay đổi) đối với mật mã học.

P so với NP theo cách dễ hiểu

P so với NP đặt câu hỏi liệu mọi bài toán có đáp án dễ kiểm tra thì cũng dễ giải hay không. Đây là một trong bảy Bài toán Thiên niên kỷ và vẫn chưa có lời giải sau tin tức này.

Câu đố Sudoku là minh họa kinh điển. Kiểm tra một lưới đã điền mất vài giây: quét từng hàng, cột và ô để tìm giá trị lặp. Tìm lời giải từ một lưới gần như trống có thể mất lâu hơn nhiều, và khoảng cách này tăng vọt khi lưới lớn dần.

• P là lớp các bài toán mà máy tính có thể giải trong thời gian đa thức, nghĩa là lượng công việc tăng như n^², n^³, v.v. khi kích thước đầu vào n tăng.
• NP là lớp các bài toán mà máy tính có thể kiểm tra một lời giải được đề xuất trong thời gian đa thức.

Mọi bài toán trong P cũng thuộc NP. Câu hỏi bỏ ngỏ là liệu chiều ngược lại có đúng không. Hầu hết các nhà khoa học máy tính tin rằng P ≠ NP, tức là một số bài toán vốn dĩ khó giải hơn kiểm tra. Mật mã hiện đại dựa trên niềm tin đó: mã hóa thì dễ, nhưng phá mã khi không có khóa phải là khó.

Giả thuyết thời gian lũy thừa là gì?

ETH còn sắc bén hơn: nó khẳng định rằng một bài toán NP cụ thể, 3-SAT, cần thời gian lũy thừa dù thuật toán có khéo léo đến đâu. Russell Impagliazzo và Ramamohan Paturi của UC San Diego đề xuất vào cuối những năm 1990, với đóng góp nền tảng của Francis Zane.

Bài toán 3-SAT

Trong 3-SAT, bạn có một công thức gồm n biến đúng/sai và một danh sách mệnh đề. Mỗi mệnh đề nối ba điều kiện bằng OR, ví dụ "x₁ đúng HOẶC x₄ sai HOẶC x₇ đúng." Nhiệm vụ là tìm một cách gán giá trị cho các biến sao cho thỏa tất cả mệnh đề cùng lúc.

Vét cạn thử mọi cách gán 2ⁿ, vì thế mỗi biến bổ sung sẽ nhân đôi khối lượng công việc. Bạn có thể thấy rằng khoảng 100 biến là bất khả thi.

ETH nói gì

ETH phát biểu rằng tồn tại một hằng số c > 1 sao cho không có thuật toán nào giải 3-SAT nhanh hơn cⁿ. Các thuật toán tinh vi có thể giảm cơ số xuống dưới 2, nhưng không bao giờ xuống mức dưới lũy thừa. Chính xác: tồn tại δ > 0 sao cho 3-SAT không thể được giải trong thời gian O(2^δn).

Trong nhiều thập kỷ, tiến bộ phù hợp với bức tranh đó. Các nhà nghiên cứu liên tục hạ cơ số, nhưng nó vẫn cao hơn 1. Vì 3-SAT có thể được chuyển đổi thành nhiều bài toán khác, ETH trở thành một giả định xương sống. Các nhà nghiên cứu dùng nó để lập luận rằng các bài toán như Clique, Vertex Cover, Independent Set và các bài toán khác cũng không thể giải nhanh hơn nhiều. 

Kết quả mới so với trước đây

Cận mới được viết tắt là 2^o(n). Chi phí cho mỗi biến bổ sung tiến dần về 1 khi n tăng, đúng như điều ETH cho là không thể.

OpenAI và Anthropic đã công bố gì

Cả hai phòng thí nghiệm độc lập đạt đến cận dưới lũy thừa về cơ bản giống nhau, và cả hai đều hậu thuẫn bài báo bằng các chứng minh được máy kiểm chứng trong trình trợ lý chứng minh Lean.

Anthropic cho biết Claude đã tìm ra thuật toán cốt lõi mà không có đầu vào từ con người sau khi tạo khoảng 14 triệu token. Phương pháp sử dụng mạng tensor và các lập luận về hạng. Sau đó các nhà nghiên cứu hỗ trợ hoàn thiện bài báo.

Tại sao cả hai phòng thí nghiệm lại tìm ra cùng ngày?

Không phòng thí nghiệm nào giải thích về thời điểm. Bài báo của Anthropic gọi hai kết quả là độc lập và đồng thời, và hai bản thảo đi theo những lộ trình toán học khác nhau để đạt cận về cơ bản giống nhau. 

Một số bối cảnh khiến sự trùng hợp kém bất ngờ hơn so với ấn tượng ban đầu. Cả hai phòng thí nghiệm đều đang hướng mô hình của họ vào danh sách dài các bài toán mở, và riêng OpenAI đã phát hành hàng trăm bản thảo toán học do AI tạo vào đầu tháng 10. ETH là một trong những mục tiêu nổi tiếng nhất trong lĩnh vực này, và cả hai mô hình đều học từ cùng kho nghiên cứu đã công bố. Phát hiện độc lập, đồng thời cũng là một khuôn mẫu lâu đời trong khoa học, như Newton và Leibniz với giải tích hay Darwin và Wallace với chọn lọc tự nhiên.

Các chứng minh chắc chắn tới mức nào?

Lean xác nhận rằng một mệnh đề hình thức suy ra hợp logic từ các tiên đề của nó. Nó không thể xác nhận rằng mệnh đề hình thức đó nói cùng điều với bài báo. Anthropic lưu ý không có máy nào kiểm tra sự khớp này, và OpenAI nói tệp Lean của họ chứng minh một cận yếu hơn chút so với tiêu đề.

Hiện nay, chính các nhà nghiên cứu đã đề xuất vấn đề, Impagliazzo và Paturi, cùng với Ryan Williams của MIT, đang tổ chức các hội thảo để đánh giá liệu các mệnh đề hình thức có thực sự nắm bắt ETH hay không. Thư của họ nhấn mạnh rằng tham gia rà soát không đồng nghĩa với ủng hộ. Tính đến thời điểm viết bài, chưa ai công khai tìm ra lỗi. 

Williams cho biết một số phần trong chứng minh của OpenAI có vẻ thường quy, trong khi "hai hoặc ba phần trông như đến từ người ngoài hành tinh" vẫn cần được xem xét kỹ. Impagliazzo, một trong các tác giả của ETH, mô tả kết quả là gây bất ngờ sâu sắc.

Điều gì thay đổi và điều gì không

Trên thực tế, hầu như không có gì thay đổi hôm nay (thở phào): các thuật toán mới chỉ vượt vét cạn trên những đầu vào lớn hơn rất nhiều so với bất kỳ máy tính nào có thể chứa.

Không có bộ giải SAT nhanh hơn

Bài báo của Anthropic nói phương pháp của họ chỉ vượt vét cạn trên các đầu vào lớn đến mức thiên văn. Với các công thức điển hình có năm mệnh đề trên mỗi biến, điểm giao cắt là một con số có khoảng 10.000 chữ số. Trong trường hợp tổng quát nhất, đó là một con số có xấp xỉ 100 triệu chữ số. 

Các tác giả cũng cho biết cách tiếp cận của họ khó có ích cho các bài toán dưới khoảng 10 triệu biến. Các bộ giải SAT dùng trong xác minh chip, lập lịch và lập kế hoạch sẽ không nhanh hơn nhờ kết quả này.

Mật mã học không bị phá vỡ

Kết quả không đụng đến P so với NP. Không ai giả vờ như vậy. OpenAI nói họ đã kiểm tra liệu thuật toán có phá các hệ mật mã thực tế hay không và khá tự tin là không. 

Lý thuyết sẽ được viết lại

Tác động lớn hơn nằm ở nghiên cứu. Các kết quả độ khó dựa trên ETH hoặc SETH giờ cần một nền tảng mới, và một số nhà nghiên cứu nói rằng nhiều năm công trình của họ có thể cần xem xét lại. Tuy nhiên không phải mọi thứ đều sụp đổ. Anthropic lưu ý kết quả này không bác bỏ bài toán vectơ trực giao, vốn nâng đỡ nhiều kết quả về độ phức tạp tinh vi. 

Tại sao điều này quan trọng với AI

Tiêu đề ít nói về 3-SAT hơn mà nói về ai đã tìm ra câu trả lời: hai hệ thống AI độc lập đã lật đổ một phỏng đoán mà các chuyên gia con người tin tưởng suốt một thế hệ.

AI như cộng tác viên nghiên cứu

Các nhà nghiên cứu nay mô tả những kết quả AI mới xuất hiện mỗi tuần hoặc hai tuần, làm gián đoạn các dự án đang thực hiện. Các công cụ hình thức như Lean đang trở nên trung tâm vì chúng cho phép con người tin cậy một chứng minh dài do máy viết mà không phải suy diễn lại từng dòng.

Lối tắt ẩn và tự cải thiện

ETH nắm bắt một niềm tin rằng một số bài toán tìm kiếm không có lối tắt khéo léo. Nếu niềm tin đó sai, những bài toán hiển nhiên là khó khác có thể cũng ẩn lối tắt.

Tôi đang nghĩ về khám phá thuật toán như một lĩnh vực mà những lối tắt như vậy có thể quan trọng rất lớn cho tự cải thiện đệ quy, tức là ý tưởng về các hệ thống AI giúp thiết kế AI tốt hơn. Dùng AI để tìm thuật toán nhanh hơn là một con đường cụ thể hướng tới điều đó, dù không có gì trong kết quả này làm được điều đó trực tiếp ngày hôm nay.

Ý nghĩa với người làm dữ liệu

Với những người xây dựng sản phẩm dựa trên dữ liệu, có ba bài học nổi bật:

• Lý thuyết độ phức tạp không chỉ là học thuật: Biết vì sao một bài toán là NP-khó giúp bạn biết khi nào nên nghĩ đến heuristic, xấp xỉ, hoặc bộ giải thay vì tìm kiếm chính xác.
• Thẩm định là một kỹ năng: Khi AI tạo ra nhiều mã và phân tích hơn, việc kiểm tra đầu ra (bằng kiểm thử, chứng minh, hoặc quy trình có thể tái lập) quan trọng không kém việc tạo ra nó.
• Giới hạn tiệm cận có thể đánh lừa: Một thuật toán “nhanh hơn” về lý thuyết có thể vô dụng ở kích thước thực tế. 

Kết luận

Nếu các chứng minh vượt qua được rà soát của chuyên gia, giả thuyết thời gian lũy thừa sẽ gia nhập danh sách ngắn những phỏng đoán được tin rộng rãi nhưng hóa ra là sai (như phỏng đoán tổng lũy thừa của Euler). Nhưng P so với NP vẫn bỏ ngỏ và mật mã học hiện vẫn an toàn.

Các cột mốc tiếp theo đáng theo dõi là các hội thảo rà soát do các tác giả gốc của ETH dẫn dắt, các bản tự triển khai độc lập của thuật toán, và liệu có ai siết chặt cận hơn nữa hay không.

Để xây nền tảng đằng sau những câu chuyện như thế này, hãy khám phá các khóa học về cấu trúc dữ liệu và thuật toán, lập trình Python, và máy học của chúng tôi. Chúng bao quát tư duy Big-O giúp những kết quả như thế này trở nên dễ đọc.