La preuve que la multiplication de la matrice ne sont pas en temps

Il est communément admis que pour tout , il est possible de multiplier deux matrices en un temps . Une discussion est ici .$\epsilon > 0$$n \times n$$O(n^{2 + \epsilon})$

J'ai demandé à des personnes plus familières avec les recherches si elles pensaient qu'il y avait un indépendant de tel qu'il existe un algorithme pour la multiplication de matrice et qu'elles semblaient avoir une écrasante majorité. l'intuition que la réponse est "non" mais ne pouvait pas expliquer pourquoi. C'est-à-dire qu'ils croient que nous pouvons le faire en un temps , mais pas en un temps .$k>0$$n$$O(n^2 \log^k n)$$O(n^{2.001})$$O(n^2 \log^{100} n)$

Quelles sont les raisons pour croire qu'il n'y a pas d' algorithme à fixé ?$O(n^2 \log^k n)$$k>0$

Il existe un algorithme pour multiplier une matrice $N \times N^{0.172}$ avec une matrice $N^{0.172} \times N$ dans les opérations arithmétiques $N^2 \operatorname{polylog}\left(N\right)$ . L’identité principale utilisée provient de l’article de Coppersmith "Multiplication rapide de matrices rectangulaires", mais l’explication de la raison pour laquelle il conduit à $N^2 \operatorname{polylog}\left(N\right)$ au lieu de $N^{2 + \epsilon}$ trouve dans l’appendice de l’ article de Williams , "Nouveaux algorithmes et bornes inférieures pour les circuits avec portes à seuil linéaire ".

Cela ne fonctionne que parce que l'identité de Coppersmith possède une structure supplémentaire dont vous pouvez tirer parti, et que les algorithmes MM les plus récents ne semblent pas avoir cette structure. Cela dit, je ne sais pas pourquoi on ne peut espérer étendre cette approche à la multiplication matricielle $N \times N \times N$

Eh bien, une chose est que je pense que toutes les constructions que nous connaissons - et même les familles de constructions potentielles que les gens ont proposées (par exemple, les approches de Cohn-Umans, les généralisations de Coppersmith-Winograd) - produiraient "simplement" une famille d'algorithmes $A_\epsilon$ courant dans le temps $O(n^{2+\epsilon})$ . Donc , pour avoir un seul algorithme qui RAN dans $O(n^2 poly(\log n))$ , il faudrait non seulement être fou asymptotiquement mieux que les approches actuelles, mais il faut regarder vraiment différent.

Gros bémol: je pense. Je n'ai jamais vraiment réfléchi à ce qu'il faudrait modifier / ajouter aux approches existantes pour pouvoir produire de manière plausible un algorithme unique s'exécutant dans le temps $O(n^2 poly(\log n))$ .

Josh Alman a montré quelques bons résultats dans la fourchette basse de MM, qui a remporté le prix du meilleur article étudiant du CCC 2019! http://drops.dagstuhl.de/opus/volltexte/2019/10834/pdf/LIPIcs-CCC-2019-12.pdf