Límites inferiores sobre la complejidad gaussiana

18

Defina la complejidad gaussiana de una matriz como el número mínimo de operaciones elementales de fila y columna requeridas para llevar la matriz a la forma triangular superior. Esta es una cantidad entre 0 y n 2 (a través de Gaussian elemination). La noción tiene sentido sobre cualquier campo.n×n0n2

Este problema ciertamente parece muy básico y debe haber sido estudiado. Sorprendentemente, no conozco ninguna referencia. Por lo tanto, estaré contento con cualquier referencia que haya. Pero, por supuesto, la pregunta principal es:

¿Hay algún límite inferior explícito no trivial conocido?

Por no trivial quiero decir superlineal. Para ser claros: sobre campos finitos, un argumento de conteo muestra que una matriz aleatoria tiene un orden de complejidad n ^ 2 (una afirmación similar debería ser verdadera sobre campos infinitos). Por lo tanto, lo que estamos buscando es una familia explícita de matrices, por ejemplo, matrices de Hadmard. Esto es lo mismo que con la complejidad del circuito booleano donde sabemos que una función aleatoria tiene una alta complejidad, pero estamos buscando funciones explícitas con esta propiedad.

Moritz
fuente
No estoy completamente seguro de cuál es la pregunta aquí. ¿Está preguntando sobre formas específicas de matrices, o el caso general (en cuyo caso un simple argumento de conteo parece funcionar)?
Joe Fitzsimons
@ Joe, como se mencionó, estoy pidiendo una familia explícita de matrices, por ejemplo, matrices Hadamard. Como de costumbre, las matrices aleatorias son trampas. Esto es muy similar a que no estamos contentos con el hecho de que una función aleatoria requiere grandes circuitos. Agregué un párrafo para enfatizar este punto.
Moritz
tal vez eso debería publicarse como respuesta :)
Suresh Venkat
Ok, lo hare.
Joe Fitzsimons
En realidad, creo que mi método puede haber sido defectuoso.
Joe Fitzsimons

Respuestas:

17

Este parece ser un problema muy difícil, relacionado con uno más ampliamente estudiado.

Supongamos que consideramos una matriz invertible cuadrada A, y definimos c (A) como el número mínimo de operaciones elementales de fila necesarias para reducir A a la matriz de identidad. Esta medida de complejidad es mayor que la que sugiere Moritz, por lo que probar límites superlineales solo puede ser más fácil.

Ahora, las operaciones de fila son reversibles . Se deduce que c (A) se puede definir de manera equivalente como el número mínimo de operaciones de fila necesarias para producir A, comenzando desde la matriz de identidad.

Tenga en cuenta que producir A de tal manera da lugar a un circuito aritmético para calcular el mapa que lleva x a Ax. El fanin de cada puerta es 2, y el número de puertas sin entrada corresponde al número de operaciones de fila.

No hay ninguna reducción obvia en la dirección inversa (de circuitos a secuencias de operaciones de fila). Aún así, podemos caracterizar c (A) en términos de la complejidad del circuito aritmético de Ax en un modelo de circuito restringido: afirmo que c (A) es igual a la mitad del número mínimo de aristas en un circuito aritmético para A, de Fanin como máximo 2 y ancho n, donde no cobramos por los bordes que conducen a las puertas de Fanin 1. (Estoy usando la noción habitual de ancho de circuito aquí). Esto se puede mostrar usando la idea simple bosquejada antes.

Ahora aquí está la conexión con problemas bien estudiados: ha sido un famoso problema abierto durante más de 30 años exhibir un mapa lineal explícito Ax (sobre cualquier campo finito) que requiere un número superlineal de puertas en un circuito fanin-2. La referencia clásica es Valiant, "Argumentos teóricos de gráficos en complejidad de bajo nivel", y una reciente encuesta FTTCS realizada por Lokam también es útil.

Al estudiar c (A), estamos imponiendo una restricción de ancho adicional, pero como nuestra restricción es tan débil (ancho n), no preveo que el problema sea mucho más fácil. Pero bueno, me encantaría que me demuestren que estoy equivocado.

Andy Drucker
fuente
2
Además, Gowers en su blog tuvo una discusión sobre la complejidad de la eliminación gaussiana. No lo he leído con atención (tiene la forma de un diálogo largo), pero puede ser útil: gowers.wordpress.com/2009/11/03/…
Andy Drucker
Solo para entender esto correctamente, ¿entra la restricción de ancho porque tiene como máximo n operaciones por columna, y puede proceder columna por columna?
Moritz
Estoy pensando en términos de operaciones de fila. La restricción de ancho n corresponde al hecho de que tenemos n filas para trabajar en las que tendría lugar todo nuestro trabajo intermedio. Las n puertas del circuito en profundidad t representan los estados de las n filas después de t aplicaciones de operaciones de fila. (tal vez estás diciendo lo mismo que yo)
Andy Drucker
Si, en cambio, permitiéramos filas adicionales de 'espacio de trabajo auxiliar' en nuestra eliminación gaussiana, creo que obtendríamos una correspondencia exacta entre la complejidad de reducir A a la identidad y la complejidad del circuito aritmético lineal de Ax (que es esencialmente la complejidad de la aritmética ckt, ya que las multiplicaciones no ayudan a calcular funciones lineales más allá de un factor constante).
Andy Drucker
Sí, a eso me refería. También estoy de acuerdo con la segunda declaración. Un circuito lineal general puede crear nuevas filas siempre que lo desee :-)
Moritz
9

Hay referencias y son bastante antiguas. Me los encontré mientras trabajaba en algoritmos combinatorios para la multiplicación de matrices booleanas.

Θ(n2/logn)logn

JW Moon y L. Moser. Un problema de reducción matricial. Matemáticas de la computación 20 (94): 328–330, 1966.

El artículo debe estar accesible en JSTOR.

Estoy bastante seguro de que el límite inferior es solo un argumento de conteo, y no se dieron matrices explícitas que logren el límite inferior.

Ryan Williams
fuente