Złożoność przestrzenna algorytmu Coppersmitha – Winograda

Algorytm Coppersmitha – Winograda jest asymptotycznie najszybszym znanym algorytmem do mnożenia dwóch macierzy kwadratowych. Czas działania ich algorytmu to który jest najlepiej znany do tej pory. Jaka jest złożoność przestrzeni tego algorytmu? Czy to jest w ?$n \times n$$O(n^{2.376})$$\Theta(n^2)$

Tak, wszystkie algorytmy wywodzące się z oryginalnego algorytmu Strassena (obejmuje to najbardziej znane algorytmy mnożenia macierzy , ale nie wszystkie - patrz komentarze) mają złożoność przestrzeni Θ ( n 2 ) . Jeśli można znaleźć n 3 - ε algorytm czasu z p o l y ( log n ) przestrzeni złożoności, byłby to wielki postęp. Jedna aplikacja to 2 ( 1 - ε ) n czas, p o l y $n^{3-\varepsilon}$$\Theta(n^2)$$n^{3-\varepsilon}$$poly(\log n)$$2^{(1-\varepsilon)n}$ algorytm przestrzenny dla problemu sumy częściowej.$poly(n)$

Istnieją jednak pewne przeszkody dla takiego wyniku. W przypadku niektórych modeli obliczeniowych istnieją dość silne dolne granice iloczynu macierzy w czasie i przestrzeni. Odniesienia takie jak Yesha i Abrahamson dadzą ci więcej informacji.