La verdadera complejidad de bits de la multiplicación de matrices es

9

La multiplicación de matrices usando Regular - técnica (fila columna interna producto) realiza multiplucations y adiciones. Sin embargo, suponiendo entradas de igual tamaño (número de bits en cada entrada de ambas matrices que se multiplican) de tamaño bits, la operación de suma en realidad ocurre en bits.O ( n 3 ) m O ( n 3 n m ) = O ( n 4 m )O(n3)O(n3)mO(n3nm)=O(n4m)

Por lo tanto, parece que la verdadera complejidad de la multiplicación de matrices si se mide a través de la complejidad de bits debería ser .O(n4)

(1) ¿Es esto correcto?

Supongamos que si se crea un algoritmo que reduce la complejidad de bits a lugar de multiplicaciones y adiciones totales, este podría ser un enfoque más sólido que, por ejemplo, reducir las multiplicaciones y adiciones totales a como lo intentaron investigadores como Coppersmith y Cohn.O ( n 2 + ϵ )O(n3+ϵ)O(n2+ϵ)

(2) ¿Es este un argumento válido?

T ....
fuente

Respuestas:

31

No, la complejidad de bits de la multiplicación de matrices en las entradas de bits es , donde es el exponente de multiplicación matricial más conocido. La multiplicación y la adición de números de bits pueden hacerse en veces. Multiplicar dos números de bits produce un número que no tiene más de bits. Al agregar números de bits cada uno, se obtiene un número que no tiene más de bits. (Piénselo: la suma es como máximo , por lo que la representación de bits no toma más den ω ( log n ) O ( 1 )M ( log M ) O ( 1 ) ω < 2.4 M M ( log M ) 2 M 2 M n M M + log n + O ( 1 ) n 2 M log ( n 2 M ) + O ( 1 )Mnorteω(Iniciar sesiónnorte)O(1)METRO(Iniciar sesiónMETRO)O(1)ω<2,4METROMETRO(Iniciar sesiónMETRO)2METRO2METROnorteMETROMETRO+Iniciar sesiónnorte+O(1)norte2METROlog(n2M)+O(1) bits)

Las referencias a algoritmos de multiplicación de enteros rápidos se pueden encontrar con una búsqueda web o wikipedia.

Ryan Williams
fuente
Creo que mi argumento fue defectuoso. Gracias. Agradezco esto.
T ....