Доказательство того, что умножение матриц происходит не за

Принято считать, что для всех $\epsilon > 0$ можно умножить две матрицы $n \times n$ за $O(n^{2 + \epsilon})$ времени. Некоторое обсуждение здесь .

Я спросил некоторых людей, которые более знакомы с исследованием, думают ли они, что существует $k>0$ независимый от $n$ такой, что существует алгоритм для умножения матриц, и они в подавляющем большинстве, похоже, имели Интуиция, что ответ «нет», но не может объяснить, почему. То есть они считают, что мы можем сделать это за время, но не за время.$O(n^2 \log^k n)$$O(n^{2.001})$$O(n^2 \log^{100} n)$

Какие есть основания полагать, что при фиксированном алгоритма ?$O(n^2 \log^k n)$$k>0$

Существует алгоритм для умножения матрицы $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}$ содержится в приложении к статье Уильямса «Новые алгоритмы». и нижние оценки для цепей с линейными пороговыми вентилями ".

Это работает только потому, что идентичность Копперсмита имеет некоторую дополнительную структуру, которой вы можете воспользоваться, и более поздние алгоритмы MM, похоже, не имеют такой структуры. Тем не менее, я не уверен, почему нельзя надеяться распространить этот подход на умножение матриц $N \times N \times N$

Ну, во-первых, я думаю, что все известные нам конструкции - и даже семейства потенциальных конструкций, которые предлагали люди (например, подходы Кон-Уманса, обобщения Копперсмита-Винограда) - "просто" создали бы семейство алгоритмов $A_\epsilon$ работает во времени $O(n^{2+\epsilon})$ . Таким образом, чтобы иметь единственный алгоритм, который выполнялся в $O(n^2 poly(\log n))$ , он должен был бы не просто быть сумасшедшим асимптотически лучше, чем существующие подходы, но и выглядеть действительно иначе.

Большое предостережение: я думаю. Я никогда не думал слишком много о том , сколько можно было бы изменить / добавить существующие подходы , чтобы они могли правдоподобно производить единый алгоритм работает во время $O(n^2 poly(\log n))$ .

Джош Алман показал отличные результаты нижней границы ММ, который получил награду CCC 2019 за лучшую студенческую работу! http://drops.dagstuhl.de/opus/volltexte/2019/10834/pdf/LIPIcs-CCC-2019-12.pdf