A prova de que a multiplicação de matrizes não está em hora

Acredita-se que, para todo , é possível multiplicar duas matrizes em . Alguma discussão está aqui .$\epsilon > 0$$n \times n$$O(n^{2 + \epsilon})$

Perguntei a algumas pessoas que estão mais familiarizadas com a pesquisa se elas pensam que existe um independente de modo que exista um algoritmo para multiplicação de matrizes, e elas parecem ter intuição de que a resposta é "não", mas não conseguiu explicar o porquê. Ou seja, eles acreditam que podemos fazê-lo no tempo , mas não no tempo .$k>0$$n$$O(n^2 \log^k n)$$O(n^{2.001})$$O(n^2 \log^{100} n)$

Que razões existem para acreditar que não há algoritmo em um fixo ?$O(n^2 \log^k n)$$k>0$

Existe um algoritmo para multiplicar uma matriz com uma matriz em operações aritméticas . A principal identidade usada para isso vem do artigo de Coppersmith "Multiplicação rápida de matrizes retangulares", mas a explicação de por que leva a vez de está no apêndice do artigo de Williams , "Novos algoritmos e limites inferiores para circuitos com limiares lineares".$N \times N^{0.172}$$N^{0.172} \times N$$N^2 \operatorname{polylog}\left(N\right)$$N^2 \operatorname{polylog}\left(N\right)$$N^{2 + \epsilon}$

Isso funciona apenas porque a identidade do Coppersmith possui uma estrutura adicional da qual você pode aproveitar, e os algoritmos MM mais recentes parecem não ter essa estrutura. Dito isto, não sei por que não se pode esperar estender essa abordagem à multiplicação de matrizes$N \times N \times N$

Bem, uma coisa é que acho que todas as construções que conhecemos - e até as famílias de construções potenciais que as pessoas propuseram (por exemplo, abordagens de Cohn-Umans, generalizações de Coppersmith-Winograd) - "simplesmente" produziriam uma família de algoritmos correndo no tempo . Portanto, para ter um único algoritmo executado em , ele teria que ser não apenas assintoticamente melhor do que as abordagens atuais, mas teria que parecer realmente diferente.$A_\epsilon$$O(n^{2+\epsilon})$$O(n^2 poly(\log n))$

Grande advertência: eu acho. Eu realmente nunca pensei muito sobre o quanto alguém teria que modificar / adicionar às abordagens existentes para que eles pudessem produzir plausivelmente um único algoritmo executando no tempo .$O(n^2 poly(\log n))$

Josh Alman mostrou alguns resultados interessantes de MM, que ganharam o CCC 2019 como melhor trabalho para estudantes! http://drops.dagstuhl.de/opus/volltexte/2019/10834/pdf/LIPIcs-CCC-2019-12.pdf