GPT-5.6 kết hợp cùng Fable: Giải mã bài toán hóc búa tồn tại suốt 25 năm

< img id="wx_img" src="https://www.qbitai.com/wp-content/uploads/imgs/qbitai-logo-1.png" width="400" height="400">

2026-08-09 17:16:58 Nguồn: QbitAI

Tác giả đã nghiên cứu từ khi còn làm nghiên cứu sinh, 17 năm sau đã được AI giải mã.

GPT-5.6 và Fable 5 đã hợp sức giải quyết một bài toán toán học hóc búa tồn tại suốt 25 năm qua.

Dimitris Papailiopoulos, nhà nghiên cứu chính tại Microsoft Research, đã chứng minh một thuật toán thời gian đa thức (polynomial-time algorithm) có thể giúp việc dò tìm MIMO đạt chính xác ngưỡng hợp lý cực đại (maximum likelihood threshold).

Tác giả cho biết quá trình này đã tiêu tốn của ông đúng bảy ngày.

Dò tìm MIMO (MIMO detection) là một vấn đề kinh điển trong lĩnh vực truyền thông không dây, đòi hỏi phía thu phải khôi phục hoàn toàn thông tin gốc từ phía phát sau khi tín hiệu đã bị nhiễu làm xáo trộn.

Về mặt thống kê, thao tác này đã có thể thực hiện được, nhưng các phương pháp trước đây đều là tìm kiếm vét cạn (exhaustive search), tiêu tốn thời gian theo cấp số mũ.

Vì vậy, vấn đề trở thành: liệu có thể khôi phục tín hiệu mà không cần tìm kiếm vét cạn, bằng cách sử dụng các thuật toán nhanh hay không?

Năm 2001, Hassibi và Vikalo tưởng rằng đã tìm ra lối thoát, nhưng đến năm 2005, con đường này lại bị Jaldén và Ottersten chứng minh là không khả thi.

Kể từ đó, giới học thuật đã lần lượt thử nghiệm các phương pháp như nới lỏng bán xác định (semidefinite relaxation), tìm kiếm cục bộ lật bit (bit-flipping local search), AMP, và các phương pháp vật lý thống kê, nhưng kết quả gần nhất cũng chỉ dừng lại ở mức cao gấp đôi ngưỡng lý thuyết.

25 năm, hết lớp học giả này đến lớp học giả khác thay phiên nhau thử sức, nhưng không ai có thể giải được bài toán này.

Suốt 25 năm, chỉ có thể dựa vào tìm kiếm vét cạn.

Dò tìm MIMO là một vấn đề cơ bản trong truyền thông không dây.

Phía phát gửi N bit qua một kênh truyền N×N, kênh truyền sẽ trộn lẫn các bit này lại với nhau và cộng thêm nhiễu;

Phía thu chỉ có trong tay một tín hiệu đã bị xáo trộn và phải tìm lại chính xác từng bit một trong số N bit ban đầu mà phía phát đã gửi.

Về lý thuyết, có một phương pháp chắc chắn thành công gọi là dò tìm hợp lý cực đại (maximum likelihood detection), tức là tính toán tất cả các tổ hợp bit có thể xảy ra để tìm ra tổ hợp khớp nhất với tín hiệu nhận được.

Phương pháp này chắc chắn tìm ra đáp án đúng, với điều kiện bạn sẵn sàng chờ đợi — N bit đồng nghĩa với 2 lũy thừa N tổ hợp, chỉ cần N lớn hơn một chút, việc tìm kiếm vét cạn sẽ kéo dài đến vô tận.

Năm 1989, Sergio Verdú đã chứng minh rằng loại vấn đề này trong trường hợp xấu nhất là NP-hard, nghĩa là dù dùng thuật toán nào, vẫn tồn tại một số đầu vào khiến khối lượng tính toán bùng nổ theo cấp số mũ.

Nhưng "trường hợp xấu nhất" nói đến các ma trận kênh được xây dựng một cách có chủ đích trong toán học để làm khó thuật toán.

Các kênh truyền không dây trong thực tế không phải do ai cố tình tạo ra, mỗi lần suy hao, mỗi lần nhiễu đều phát sinh ngẫu nhiên, không chọn những trường hợp khó tính nhất để làm khó phía thu.

Do đó, từ đầu những năm 2000, giới học thuật bắt đầu đặt ra một câu hỏi cụ thể hơn —

Nếu kênh truyền phát sinh ngẫu nhiên, miễn là về mặt thống kê có khả năng khôi phục các bit gốc, liệu có nhất thiết phải tìm ra một thuật toán không cần tìm kiếm vét cạn hay không?

Các nghiên cứu sau đó đã đưa ra một ranh giới chính xác: khi tỷ lệ tín hiệu trên nhiễu (SNR) đạt đến 2logN, xác suất để các bit được gửi đi có thể khôi phục hoàn toàn sẽ tiến dần đến 1.

Dưới ngưỡng này, ngay cả phương pháp dò tìm hợp lý cực đại cũng bắt đầu sai sót, vì vậy ranh giới này được gọi là ngưỡng hợp lý cực đại (maximum likelihood threshold).

Vấn đề trở nên cụ thể hơn — liệu có thể thiết kế một thuật toán chạy nhanh, đạt chính xác ngưỡng hợp lý cực đại hay không?

Năm 2001, Babak Hassibi và Haris Vikalo tưởng rằng đã tìm ra câu trả lời.

Họ phân tích một thuật toán gọi là giải mã hình cầu (sphere decoder).

Thuật toán này trước tiên vạch ra một "hình cầu" xung quanh tín hiệu nhận được, chỉ tìm kiếm trong số các ứng viên nằm trong hình cầu đó và bỏ qua những gì nằm ngoài, nhờ bước này để thu hẹp phạm vi tìm kiếm.

Hassibi và Vikalo đã suy ra công thức độ phức tạp kỳ vọng của thuật toán này, kết quả cho thấy nó có thời gian đa thức.

Nếu kết luận này đúng, bài toán này về cơ bản đã được giải quyết.

Nhưng năm 2005, Joakim Jaldén và Björn Ottersten đã bác bỏ kết luận này.

Họ chứng minh rằng ở bất kỳ tỷ lệ tín hiệu trên nhiễu cố định nào, độ phức tạp kỳ vọng của giải mã hình cầu thực chất là theo cấp số mũ, chứ không phải đa thức.

Lý do là để bao trọn tín hiệu gửi đi vào trong "hình cầu" với xác suất không tiến về 0, bán kính hình cầu phải tăng lên cùng với quy mô của vấn đề; một khi hình cầu lớn lên, số lượng ứng viên cần tìm kiếm bên trong cũng tăng theo cấp số mũ.