Complexidade espacial do algoritmo Coppersmith – Winograd

O algoritmo de Coppersmith – Winograd é o algoritmo conhecido mais rapidamente assintoticamente para multiplicar duas matrizes quadradas. O tempo de execução de seu algoritmo é o mais conhecido até o momento. Qual é a complexidade espacial deste algoritmo? Está em ?O ( n 2.376 ) Θ ( n 2$n \times n$$O(n^{2.376})$$\Theta(n^2)$

Sim, todos os algoritmos originários do algoritmo original de Strassen (isso inclui os algoritmos mais conhecidos para multiplicação de matrizes, mas não todos - veja os comentários) têm complexidade espacial . Se você pudesse encontrar um algoritmo de tempo com complexidade de espaço , isso seria um grande avanço. Uma aplicação seria um algoritmo de tempo, espaço para o problema de Subconjunto-Soma. q ( 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)$

No entanto, existem alguns obstáculos para esse resultado. Para alguns modelos computacionais, existem limites inferiores bastante fortes para o produto espaço-tempo da multiplicação de matrizes. Referências como Yesha e Abrahamson fornecerão mais informações.