True Bit A complexidade da multiplicação de matrizes é

9

A multiplicação de matrizes usando a técnica regular (produto interno da coluna de linha) utiliza multiplicações e O ( n 3 ) adições. No entanto, assumindo entradas de tamanho igual (número de bits em cada entrada de ambas as matrizes sendo multiplicadas) de tamanho m bits, a operação de adição realmente acontece nos bits O ( n 3 n m ) = O ( n 4 m ) .O(n3)O(n3)mO(n3nm)=O(n4m)

Portanto, parece que a verdadeira complexidade da multiplicação de matrizes, se medida pela complexidade dos bits, deve ser .O(n4)

isso é correto?(1)

Supondo que, se alguém cria um algoritmo que reduz a complexidade do bit a vez de multiplicações e adições totais, isso pode ser uma abordagem mais sólida do que, por exemplo, reduzir o número total de multiplicações e adições a O ( n 2 + ϵ ), como tentativa por pesquisadores como Coppersmith e Cohn.O(n3+ϵ)O(n2+ϵ)

Esse argumento é válido?(2)

T ....
fonte

Respostas:

31

Mnω(logn)O(1)M(logM)O(1)ω<2.4MM(logM)2M2MnMM+logn+O(1)n2Mlog(n2M)+O(1)

Referências a algoritmos de multiplicação rápida de números inteiros podem ser encontradas em uma pesquisa na web ou na wikipedia.

Ryan Williams
fonte
Eu acho que meu argumento foi falho. Obrigado. Eu aprecio isso.
T ....