Math Labs

Bài toán mở, Toán ứng dụng và Tính toán, Đại số, nêu năm 1969

Số mũ nhân ma trận ω\omega

Còn mở

Gọi ω\omega là cận dưới đúng của mọi số thực τ\tau sao cho hai ma trận cỡ n×nn \times n trên một trường có thể nhân với nhau bằng O(nτ)O(n^\tau) phép toán số học. Hãy xác định giá trị chính xác của ω\omega; cụ thể, liệu có phải ω=2\omega = 2 hay không?

Hiện trạng nghiên cứu tính đến năm 2026

Tính đến năm 2026, giá trị chính xác của ω\omega vẫn còn mở trong khoảng từ 22 đến 2.3711772.371177. Các đột phá giai đoạn 2023–2024 của Duan, Wu, Zhou và của Alman, Duan, Vassilevska Williams, Xu, Xu, Zhou đã hạ ω\omega xuống 2.3713392.371339 nhờ phân tích tổn hao tổ hợp bất đối xứng trong phương pháp laser, và một preprint năm 2026 của Dupont cùng cộng sự đã đẩy bài toán tối ưu mức 44 xuống ω<2.371177\omega < 2.371177. Tuy nhiên, các kết quả rào cản chỉ ra rằng riêng họ tensor Coppersmith–Winograd không thể đạt tới ω=2\omega = 2.

Kết quả tốt nhất đã biết

  • Các cải tiến phương pháp laser đã công bố dùng phân tích tổn hao tổ hợp bất đối xứng thiết lập ω<2.371339\omega < 2.371339 (Alman, Duan, Vassilevska Williams, Xu, Xu và Zhou 2024/2025), cùng một preprint năm 2026 của Dupont và cộng sự chứng nhận ω<2.371177\omega < 2.371177.
  • Ambainis, Filmus và Le Gall (2015) chứng minh rằng phương pháp laser áp dụng cho các lũy thừa của tensor Coppersmith–Winograd không thể chứng minh được ω<2.3078\omega < 2.3078.

Công cụ và chỗ dừng

Công cụĐạt đượcChỗ dừng
Phương pháp laser của Strassen và phân tích tổn hao tổ hợp bất đối xứngLiên tiếp hạ cận trên của ω\omega từ 2.4792.479 xuống 2.3711772.371177 bằng cách phân tích các lũy thừa tensor bậc cao của tensor Coppersmith–WinogradVấp phải các rào cản bản chất (như ω≥2.3078\omega \ge 2.3078 đối với họ Coppersmith–Winograd) và sự bùng nổ hàm mũ kép của số tham số tối ưu theo mức đệ quy
Hạng biên và bất đẳng thức tổng tiệm cậnChuyển các phân rã xấp xỉ của tổng trực tiếp các tensor nhân ma trận thành cận trên tiệm cận hợp lệ cho ω\omegaĐòi hỏi phải tìm được các tensor khởi đầu có hạng biên thấp và giá trị cao, nhưng chưa họ tensor đã biết nào tiến gần tới ω=2\omega = 2

Câu hỏi còn mở

  • Liệu có phải ω=2\omega = 2, tức là hai ma trận n×nn \times n có thể nhân được trong O(n2+ε)O(n^{2 + \varepsilon}) phép toán với mọi ε>0\varepsilon > 0?
  • Có thể chứng minh cận dưới vô điều kiện nào mạnh hơn bậc 2n22n^2 phép toán số học cho mạch số học tổng quát nhân hai ma trận n×nn \times n hay không?

Tài liệu tham khảo

  1. Volker Strassen (1969). Gaussian elimination is not optimal · DOI:10.1007/BF02165411
  2. Don Coppersmith, Shmuel Winograd (1990). Matrix multiplication via arithmetic progressions · DOI:10.1016/S0747-7171(08)80013-2
  3. Ran Duan, Hongxun Wu, Renfei Zhou (2023). Faster Matrix Multiplication via Asymmetric Hashing · DOI:10.1109/FOCS57990.2023.00035 · arXiv:2210.10173
  4. Josh Alman, Ran Duan, Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu, Renfei Zhou (2024). More Asymmetry Yields Faster Matrix Multiplication · arXiv:2404.16349