Mô hình tiếp theo của OpenAI, Astra, vừa giải mười bài toán mở tồn đọng hàng thập kỷ

Ngày 1 tháng 8, OpenAI công bố một báo cáo cho biết mô hình tiếp theo của họ, tên nội bộ là Astra (chưa phát hành), đã đưa ra kết quả mới cho mười bài toán mở khác nhau trong toán học. (Không, đó không phải là các bài toán Giải thưởng Thiên niên kỷ, nhưng vẫn rất quan trọng.)

Điểm đáng chú ý: Những lời giải này không phải là các bước tiến dần dần trên những bài toán đó; chúng là các lời giải trọn vẹn, được kiểm chứng bằng Lean. (Lean là một ngôn ngữ lập trình và công cụ trợ lý chứng minh buộc mọi bước trong lập luận toán học phải được trình bày chi tiết ở dạng máy có thể đọc được.) 

Có rất nhiều điều để tiếp nhận cùng lúc. Trong bài viết này, tôi sắp xếp các bài toán theo lĩnh vực và mô tả ở mức khái quát những gì đã xảy ra, điều này có thể hàm ý gì cho toán học với tư cách là một ngành, và rút ra những gì khác chúng ta có thể biết về Astra.

Mười bài toán là gì?

Dưới đây là từng kết quả, bằng ngôn từ dễ hiểu, cùng với lĩnh vực toán học hoặc khoa học máy tính tương ứng.

Nhóm không sofic

Lĩnh vực: Lý thuyết nhóm

Astra đã đưa ra một xây dựng tường minh của một nhóm không thể được xấp xỉ, dù sát đến đâu, bằng các cấu trúc hữu hạn lớn — khép lại một câu hỏi mở kể từ khi khái niệm nhóm “sofic” được giới thiệu năm 1999. Bản xây dựng đi kèm một chứng minh rằng không có dãy xấp xỉ hữu hạn nào có thể hiệu quả, được hình thức hóa trong Lean để logic có thể được kiểm tra cơ học.

Wikipedia đã được cập nhật:

Đóng gói hình cầu

Lĩnh vực: Hình học chiều cao

Câu hỏi là có thể đóng gói các hình cầu đồng nhất, không chồng lấn dày đặc đến mức nào khi số chiều tăng lên. Astra đã chứng minh một trần chặt chẽ hơn cho mật độ đó ở chiều cao, là cải thiện đầu tiên cho cận cụ thể này kể từ năm 1978. Nó không đưa ra một phương pháp đóng gói tốt hơn — mà thu hẹp giới hạn mức độ tốt tối đa mà bất kỳ phương pháp tương lai nào có thể đạt được.

Mã nhị phân và mã cầu

Lĩnh vực: Lý thuyết mã

Mã hiệu chỉnh lỗi hoạt động bằng cách giữ các thông điệp hợp lệ đủ xa nhau để các lỗi nhỏ không thể biến thông điệp này thành thông điệp khác. Astra đã chứng minh các giới hạn chặt chẽ hơn đáng kể (cải thiện theo hàm mũ) về số lượng thông điệp như vậy có thể tồn tại với một khoảng cách tối thiểu cho trước, cùng một kết quả tương ứng cho các điểm trải trên một mặt cầu nhiều chiều.

Giả thuyết độ cứng của Connes

Lĩnh vực: Đại số toán tử

Alain Connes giả thuyết rằng một số nhóm nhất định luôn có thể được tái thiết duy nhất từ một cấu trúc đại số, gọi là đại số von Neumann, được xây dựng từ chúng. Astra đã bác bỏ điều này bằng cách đưa ra hai nhóm thực sự khác nhau nhưng tạo ra cùng một đại số, cho thấy phép tái thiết không phải lúc nào cũng một-một.

Độ phức tạp mạch số học

Lĩnh vực: Lý thuyết độ phức tạp tính toán

“Permanent”, một con số duy nhất được tính từ một lưới số, rất tốn kém để tính, và các nhà lý thuyết độ phức tạp muốn biết số bước số học tối thiểu mà bất kỳ phương pháp nào có thể cần. Astra đã chứng minh một cận dưới mới, mạnh hơn cho mức tối thiểu đó — một dạng kết quả nổi tiếng là khó cải thiện dù chỉ một chút.

Lặp song song lượng tử

Lĩnh vực: Lý thuyết độ phức tạp lượng tử

Lý thuyết cổ điển nói rằng buộc hai người chơi không liên lạc lặp lại một trò chơi khó nhiều lần song song sẽ khiến gian lận có khả năng thành công giảm theo hàm mũ. Astra đã chứng minh đảm bảo tương tự vẫn đúng ngay cả khi người chơi chia sẻ vướng víu lượng tử, mở rộng một nguyên lý cổ điển nền tảng sang bối cảnh lượng tử.

Bài toán vectơ gần nhất

Lĩnh vực: Mật mã dựa trên mạng

Với một lưới điểm lặp lại (mạng) và một vị trí mục tiêu, bài toán yêu cầu điểm lưới gần nhất — một bài toán được cho là rất khó ở chiều cao, đó là lý do nó là nền tảng cho một số dạng mã hóa chống lượng tử. Astra đã chứng minh rằng ngay cả việc xấp xỉ đáp án, trong một hệ số đa thức cụ thể, vẫn chứng minh được là khó, củng cố nền tảng mật mã xây dựng dựa trên nó.

Giả thuyết thể tích của Ehrhart

Lĩnh vực: Hình học rời rạc và lồi

Với một dạng hình lồi mà điểm lưới nội duy nhất nằm chính xác tại trọng tâm của nó, các nhà toán học muốn biết thể tích lớn nhất mà dạng hình như vậy có thể có trong bất kỳ số chiều nào. Astra đã tìm ra thể tích cực đại đó cho mọi số chiều, giải quyết giả thuyết ở mức tổng quát đầy đủ.

Số Ramsey đa màu

Lĩnh vực: Lý thuyết Ramsey / tổ hợp

Với đủ nhiều người và đủ nhiều loại mối quan hệ giữa họ, cuối cùng bạn sẽ đảm bảo tìm thấy ba người đều được kết nối bởi cùng một loại. Astra đã chứng minh rằng kích thước nhóm tối thiểu cần thiết tăng nhanh hơn bất kỳ tốc độ hàm mũ cố định nào khi số loại tăng, giải quyết bài toán Erdős số 183.

Các giả thuyết về số cực trị

Lĩnh vực: Lý thuyết đồ thị cực trị

Nhánh toán học này hỏi một mạng có thể có bao nhiêu kết nối trong khi vẫn tránh được một số mẫu nhỏ bị cấm. Astra đã giải quyết hai giả thuyết liên quan ở đây, tương ứng với các bài toán Erdős số 146 và 180, xác định mật độ mà các mạng như vậy có thể đạt tới trước khi những mẫu đó trở nên không thể tránh khỏi.

Mỗi bài toán trong số này đã mở ít nhất một thập kỷ; một số đã tồn tại ba mươi năm hoặc hơn, bao gồm cả các bài toán được các chủ nhân Giải Turing trong mảng khoa học máy tính lý thuyết nghiên cứu.

Khoan đã, phản ví dụ có phải là kiểu chứng minh “dễ” không?

Tôi không dám nói điều gì tiêu cực ở đây, nhưng tôi biết đây là câu hỏi hay phản ứng thường gặp, đặc biệt từ những người có hiểu biết về toán.

Điều người ta thường nói nhất, như một phê bình: Một số kết quả này là các phản ví dụ hơn là một lý thuyết tổng quát mới. Ý này quan trọng vì một phản ví dụ trả lời câu hỏi có/không nhưng tự nó không cho bạn biết vì sao mô hình bị phá vỡ hoặc cung cấp cho bạn một họ đối tượng tương tự để nghiên cứu tiếp, trong khi thứ khác, như định lý phân loại hay một kỹ thuật mới, mở ra nhiều cánh cửa hơn.

Tôi cho rằng phê bình này đúng nói chung, nhưng nó không thể dùng để gạt bỏ cả loạt bài toán này. Thứ nhất, kết quả về nhóm không sofic không phải là một tinh chỉnh nhỏ cho một gần đúng sẵn có — đó là bản xây dựng đầu tiên thuộc loại này sau 27 năm mà không ai có được, và kỹ thuật đằng sau được kỳ vọng sẽ khái quát hóa để tìm ra các ví dụ khác.

Thứ hai, một số trong chín kết quả còn lại, bao gồm cận đóng gói cầu và tính khó của CVP, không phải là phản ví dụ; chúng là các cải thiện trực tiếp cho những cận hiện hành. 

Những điều còn bỏ ngỏ

Một vài điều đáng theo dõi khi cộng đồng bóc tách vấn đề này trong những ngày, tuần và tháng tới:

• Chưa có phản biện ngang hàng. Các kết quả được Lean kiểm chứng và được các nhà toán học đã xem bản thảo tiền in đánh giá không chính thức, nhưng chưa cái nào qua quy trình tạp chí phản biện. 
• Tác quyền vẫn đang được thương lượng. OpenAI cho biết họ chịu trách nhiệm về bản thảo và hình thức hóa bằng Lean, trong khi quy gán các lập luận toán học tự thân cho mô hình. Việc tái lập độc lập quy trình (khác với việc xác minh các chứng minh) hiện vẫn khó thực hiện.

Điều này có ý nghĩa gì với toán học

Sự thay đổi tức thời nhất nằm ở việc các nhà toán học có thể thực sự dành thời gian cho điều gì. Nếu một bài toán mở được đặt tốt có thể chuyển cho một mô hình và kiểm tra bằng Lean, điểm nghẽn chuyển từ “có ai giải được không” sang “chúng ta đã đặt câu hỏi đúng và hình thức hóa chính xác chưa”. Kỹ năng đặt một bài toán hay và biết bài nào đáng tấn công là một kỹ năng thực sự mà các nhà toán học tích lũy qua trải nghiệm. 

Cũng có một câu hỏi về tài trợ và uy tín đang âm ỉ. Các khoản tài trợ nghiên cứu, hồ sơ lên chức và giải thưởng lịch sử vốn dựa trên sự khan hiếm: những bài toán này đủ khó để việc giải được một bài nói lên điều gì đó về người giải. Nếu các kết quả có AI hỗ trợ trở nên thường quy, ngành sẽ cần những cách mới để biểu thị điều gì thực sự khó so với điều gì nay đã nằm trong tầm với với vài nghìn đô chi phí suy luận. Tất nhiên, công chúng trung bình không thật sự hiểu các bài toán này. Những người có đào tạo thực sự thì hiểu, và điều đó không thay đổi. Vì thế tri thức toán học còn giá trị hơn bao giờ hết. 

Mọi người đang phản ứng ra sao

Phản ứng trên mạng xã hội ít chia rẽ về việc các chứng minh có qua kiểm tra hay không, mà nhiều hơn về việc chúng là bằng chứng cho điều gì.

Một số người xem chính tốc độ là câu chuyện lớn: mười bài toán tồn tại hàng thập kỷ xuất hiện cùng lúc, trải rộng các lĩnh vực không liên quan, nhanh hơn tốc độ chuyên gia có thể thẩm định. Câu hỏi cho tương lai: “Chúng ta có theo kịp việc kiểm tra tất cả điều này không?”

Những người khác phản biện rằng điều này nói ít hơn về AI nói chung so với vẻ bề ngoài. Toán học là một lĩnh vực hiếm hoi nơi công việc của mô hình có thể được kiểm tra tự động và hoàn toàn. Hầu hết các vấn đề trong thế giới thực không có sẵn dạng “đáp án tự động” như vậy. Theo góc nhìn đó, thành tựu là có thật, nhưng có lẽ nói lên nhiều hơn về việc toán học đặc biệt phù hợp với AI.

Một luồng bình luận thứ ba: Một chứng minh đúng mà chưa ai kiểm toán hay thấu hiểu trọn vẹn thì chưa thực sự được hiểu, chỉ mới được kiểm chứng. Khám phá một định lý và hiểu nó có ý nghĩa gì, theo góc nhìn này, là hai công việc khác nhau.

Lời kết

Các nhà toán học cho rằng kết quả về nhóm không sofic có vẻ là thứ “xịn”: một câu hỏi mở thực sự, kéo dài hàng thập kỷ trong lý thuyết nhóm, được khép lại bằng một xây dựng tường minh mà các nhà toán học trong ngành đang nghiêm túc đón nhận. Chín kết quả còn lại, xét chung, đại diện cho một loạt tiến bộ rộng và có chiều sâu kỹ thuật trong toán học thuần túy.

Điều chưa diễn ra là phần chậm hơn: phản biện ngang hàng, tái lập quy trình tìm kiếm, và việc cộng đồng thực sự xây dựng tiếp dựa trên các kết quả này. Phần đó mất nhiều thời gian hơn một bài blog, và chính nó sẽ cho chúng ta biết mức độ “lớn” của sự kiện này. Chúng tôi sẽ tiếp tục cập nhật.