Complejidad espacial del algoritmo Coppersmith – Winograd

El algoritmo de Coppersmith-Winograd es el algoritmo conocido asintóticamente más rápido para multiplicar dos matrices cuadradas. El tiempo de ejecución de su algoritmo es que es el más conocido hasta ahora. ¿Cuál es la complejidad espacial de este algoritmo? ¿Está en ?$n \times n$$O(n^{2.376})$$\Theta(n^2)$

Sí, todos los algoritmos que se derivan del algoritmo original de Strassen (esto incluye los algoritmos más conocidos para la multiplicación de matrices, pero no todos; vea los comentarios) tienen complejidad espacial . Si pudiera encontrar un algoritmo de tiempo con complejidad de espacio , este sería un gran avance. Una aplicación sería un algoritmo de espacio 2 ( 1 - ε ) n tiempo, p o l y ( n ) para el problema Subset-Sum.$n^{3-\varepsilon}$$\Theta(n^2)$$n^{3-\varepsilon}$$poly(\log n)$$2^{(1-\varepsilon)n}$$poly(n)$

Sin embargo, hay algunos obstáculos para tal resultado. Para algunos modelos computacionales, existen límites inferiores bastante fuertes para el producto espacio-temporal de la multiplicación de matrices. Referencias como Yesha y Abrahamson le darán más información.