Estoy tratando de entender la relación entre la complejidad algorítmica y la complejidad del circuito de los determinantes y la multiplicación de matrices.
Se sabe que el determinante de una matriz se puede calcular en el tiempo , donde es el tiempo mínimo requerido para multiplicar dos matrices. También se sabe que la mejor complejidad del circuito de los determinantes es polinomial en la profundidad y exponencial en la profundidad 3. Pero la complejidad del circuito de la multiplicación de matrices, para cualquier profundidad constante, es solo polinomial.
¿Por qué hay una diferencia en la complejidad del circuito para los determinantes y la multiplicación de matrices, mientras se sabe que desde la perspectiva del algoritmo el cálculo de determinantes es similar a la multiplicación de matrices? Específicamente, ¿por qué las complejidades del circuito tienen una brecha exponencial en la profundidad- ?
Probablemente, la explicación es simple pero no la veo. ¿Hay alguna explicación con 'rigor'?
También busque en: La fórmula más pequeña conocida para el determinante
Yo diría que la brecha en la configuración aritmética nos dice que la multiplicación de matrices es inherentemente una tarea mucho más paralela que el determinante. En otras palabras, si bien las complejidades secuenciales de ambos problemas están estrechamente relacionadas, sus complejidades paralelas no están tan próximas entre sí.
Un artículo relevante es Algoritmos de inversión de matriz paralela rápida de Csanky donde demuestra que la complejidad aritmética de calcular el determinante de una matriz (es decir, la profundidad de un circuito aritmético que calcula el determinante) satisface Que yo sepa, estos siguen siendo los límites más conocidos para este problema. Esto tiene que ser comparado con el circuito aritmético trivial de profundidad- que calcula una multiplicación matricial, dada por la fórmula .D(n) n×n
fuente