Raumkomplexität des Coppersmith-Winograd-Algorithmus

Der Coppersmith-Winograd-Algorithmus ist der asymptotisch schnellste bekannte Algorithmus zum Multiplizieren von zwei Quadratmatrizen. Die Laufzeit ihres Algorithmus ist , die bisher bekannteste. Was ist die Raumkomplexität dieses Algorithmus? Liegt es in ?O ( n 2,376 ) Θ ( n 2$n \times n$$O(n^{2.376})$$\Theta(n^2)$

Ja, alle Algorithmen, die aus Strassens ursprünglichem Algorithmus stammen (dies schließt die bekanntesten -Algorithmen für die Matrixmultiplikation ein, aber nicht alle - siehe die Kommentare), haben die Raumkomplexität . Wenn Sie einen -Zeitalgorithmus mit finden könnten , wäre dies ein großer Fortschritt. Eine Anwendung wäre eine Zeit, Raum Algorithmus für das Subset-Sum Problem. & THgr; ( 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)$

Es gibt jedoch einige Hindernisse für ein solches Ergebnis. Für einige Rechenmodelle gibt es ziemlich starke Untergrenzen für das Zeit-Raum-Produkt der Matrixmultiplikation. Referenzen wie Yesha und Abrahamson geben Ihnen weitere Informationen.