Пространственная сложность алгоритма Копперсмита – Винограда

Алгоритм Копперсмита – Винограда - это асимптотически самый быстрый известный алгоритм для умножения двух квадратных матриц. Время выполнения их алгоритма - который является самым известным на сегодняшний день. Какова пространственная сложность этого алгоритма? Это в ?O ( n 2,337 ) Θ ( n 2$n \times n$$O(n^{2.376})$$\Theta(n^2)$

Да, все алгоритмы, основанные на оригинальном алгоритме Штрассена (включая большинство известных алгоритмов для умножения матриц, но не все - см. Комментарии), имеют пространственную сложность . Если бы вы могли найти алгоритм времени со сложностью пространства , это было бы большим достижением. Одним из применений будет алгоритм пространства времени, для задачи о подмножестве сумм. Θ ( n 2 ) n 3 - ε p o l y ( log n ) 2 ( 1 - ε ) n p o l y ( n $n^{3-\varepsilon}$$\Theta(n^2)$$n^{3-\varepsilon}$$poly(\log n)$$2^{(1-\varepsilon)n}$$poly(n)$

Однако есть некоторые препятствия для такого результата. Для некоторых вычислительных моделей существуют довольно сильные нижние оценки пространственно-временного произведения умножения матриц. Ссылки, такие как Йеша и Абрахамсон , дадут вам больше информации.