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 )
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 .
¿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 + ϵ )
¿Es este un argumento válido?