Definição de expoente de multiplicação de matrizes

Coloquialmente, a definição do expoente de multiplicação de matrizes é o menor valor para o qual existe um algoritmo conhecido de multiplicação de matrizes . Como não é aceitável como definição matemática formal, acho que a definição técnica é algo como o mínimo em todo tal forma que existe um algoritmo de multiplicação de matrizes em .n ω t n $\omega$$n^{\omega}$$t$$n^t$

Nesse caso, não podemos dizer que existe um algoritmo para multiplicação de matrizes em ou mesmo , apenas que para todo existe um algoritmo em . Muitas vezes, no entanto, trabalhos e resultados que usam multiplicação de matrizes relatam seu custo simplesmente como . n ω + o ( 1 ) ϵ > 0 n ω + ϵ O ( n ω$n^{\omega}$$n^{\omega + o(1)}$$\epsilon > 0$$n^{\omega + \epsilon}$$O(n^{\omega})$

Existe alguma definição alternativa de que permita esse uso? Existem resultados que garantem que um algoritmo de tempo ou n ^ {\ omega + o (1)} exista? Ou o uso O (n ^ {\ omega}) é simplesmente desleixado?n ω n ω + o ( 1 ) O ( n ω$\omega$$n^{\omega}$$n^{\omega + o(1)}$$O(n^{\omega})$

O expoente de multiplicação de matrizes não garante que exista um algoritmo executado no tempo , mas apenas que para cada , existe um algoritmo executado em . De fato, se você puder encontrar um algoritmo que seja executado no tempo , isso mostrará que .$\omega$$O(n^\omega)$$\epsilon > 0$$O(n^{\omega+\epsilon})$$O(n^2 \mathrm{polylog}(n))$$\omega = 2$

Você pode encontrar a definição formal no livro Teoria da Complexidade Algébrica de Peter Bürgisser, Michael Clausen, Amin Shokrollahi.

Um comentário menor que é muito longo para ser um comentário:

Às vezes, quando você tem um problema para o qual existe um algoritmo com tempo de execução para cada ϵ > 0 , existe um algoritmo com tempo de execução n k + o ( 1 ) .$O(n^{k+\epsilon})$$\epsilon>0$$n^{k+o(1)}$

Por exemplo, às vezes você obtém algoritmos que funcionam como para alguma função de crescimento rápido f (como 2 2 1 / ϵ ). Se você definir f ( 1 / ϵ ) para (digamos) log n , ϵ será o (1). No exemplo com f ( 1 / ϵ ) sendo 2 2 1 / ϵ , você pode escolher 1 /$f(1/\epsilon)n^{k+\epsilon}$$f$$2^{2^{1/\epsilon}}$$f(1/\epsilon)$$\log n$$\epsilon$$f(1/\epsilon)$$2^{2^{1/\epsilon}}$$1/\epsilon$seja , que fornece ϵ = 1 / ( log log log n ) , que é o (1). Portanto, o tempo de execução final desse algoritmo será n k + o ( 1 ) , uma vez que log n também é n o ( 1 ) .$\log \log \log n$$\epsilon = 1/ (\log \log \log n)$$n^{k+o(1)}$$\log n$$n^{o(1)}$

É bem sabido o resultado de Coppersmith e Winograd que o tempo não pode ser realizado por nenhum algoritmo isolado. Mas eu li que eles se restringiam a algoritmos baseados em identidades bilineares do tipo Strassen, então não tenho certeza, já que o jornal está por trás de um paywall.$O(n^{\omega})$

Não concordo com sua afirmação na pergunta de que não está bem definido pelo "menor valor para o qual existe um algoritmo conhecido de multiplicação de matrizes n ω ". Quando as pessoas estão usando essa constante, é porque seu algoritmo se baseia em uma multiplicação de matrizes e, por uma complexidade n ω , elas significam "a complexidade ideal de nosso algoritmo é dada pelo algoritmo ideal de multiplicação de matrizes".$\omega$$n^ω$$n^\omega$

Não estou dizendo que não seja possível definir outra maneira (por exemplo, dizendo que ω é a melhor complexidade possível).$\omega$$\omega$

Aliás, o limite superior mais conhecido para multiplicação de matrizes foi aprimorado para se não me engano. $2.3737$