Considere el siguiente problema:
Dada una matriz , queremos optimizar el número de adiciones en el algoritmo de multiplicación para calcular .v ↦ M v
Este problema me parece interesante debido a su relación con la complejidad de la multiplicación de matrices (este problema es una versión restringida de la multiplicación de matrices).
¿Qué se sabe sobre este problema?
¿Hay resultados interesantes que relacionen este problema con la complejidad del problema de multiplicación de matrices?
La respuesta al problema parece involucrar encontrar circuitos con solo puertas de adición. ¿Qué pasa si permitimos puertas de resta?
Estoy buscando reducciones entre este problema y otros problemas.
Motivado por
Respuestas:
Este es esencialmente el problema que motivó a Valiant a introducir la rigidez de la matriz en la complejidad (hasta donde yo entiendo la historia).
Un circuito lineal es un circuito algebraico cuyas únicas puertas son puertas de combinación lineal de dos entradas. Cada transformación lineal (matriz) puede calcularse mediante un circuito lineal de tamaño cuadrático, y la pregunta es cuándo se puede mejorar. Se sabe que para una matriz aleatoria no se puede mejorar significativamente.
Algunas matrices, como la matriz de transformación de Fourier, una matriz de bajo rango o una matriz dispersa, se pueden hacer significativamente mejor.
Una matriz suficientemente rígida no puede ser calculada por circuitos lineales que sean simultáneamente de tamaño lineal y profundidad logarítmica (Valiant), pero hasta el día de hoy no se conocen matrices explícitas para las cuales haya un límite inferior superlineal en el tamaño de los circuitos lineales.
No recuerdo haber visto resultados que digan que es difícil calcular el tamaño del circuito lineal más pequeño para una matriz dada, pero no me sorprendería si fuera NP-hard.
fuente
Estos límites son esencialmente los mejores posibles. Ver Capítulo 6.3. en el libro de Chazelle .
fuente