Limites inferiores na complexidade gaussiana

18

Defina a complexidade gaussiana de uma matriz para ser o número mínimo de operações elementares de linha e coluna necessárias para trazer a matriz para a forma triangular superior. Essa é uma quantidade entre e (via eliminação gaussiana). A noção faz sentido sobre qualquer campo.n×n0n2

Esse problema certamente parece muito básico e deve ter sido estudado. Surpreendentemente, não conheço nenhuma referência. Então, eu vou ser feliz com qualquer referência que existe. Mas, claro, a questão principal é:

Existem limites inferiores explícitos não triviais conhecidos?

Por não trivial, quero dizer superlinear. Só para esclarecer: Sobre campos finitos, um argumento de contagem mostra que uma matriz aleatória tem ordem de complexidade n ^ 2 (uma afirmação semelhante deve ser verdadeira sobre campos infinitos). Portanto, o que estamos procurando é uma família explícita de matrizes, por exemplo, matrizes de Hadmard. É o mesmo da complexidade do circuito booleano, onde sabemos que uma função aleatória tem alta complexidade, mas estamos procurando funções explícitas com essa propriedade.

Moritz
fonte
Não tenho muita certeza de qual é a questão aqui. Você está perguntando sobre formas específicas de matrizes ou o caso geral (nesse caso, um simples argumento de contagem parece funcionar)?
Joe Fitzsimons
@ Joe, como mencionado, estou pedindo uma família explícita de matrizes, por exemplo, matrizes Hadamard. Como sempre, matrizes aleatórias estão trapaceando. Isso ocorre da mesma maneira que não estamos felizes com o fato de que uma função aleatória requer grandes circuitos. Eu adicionei um parágrafo para enfatizar esse ponto.
Moritz
talvez que deve ser anunciado como uma resposta :)
Suresh Venkat
Ok, vai fazer isso.
Joe Fitzsimons
Na verdade, acredito que meu método pode ter sido falho.
Joe Fitzsimons

Respostas:

17

Esse parece ser um problema muito difícil, relacionado a um problema mais amplamente estudado.

Suponha que consideremos uma matriz quadrada invertível A e definimos c (A) como o número mínimo de operações de linha elementares necessárias para reduzir A à matriz de identidade. Essa medida de complexidade é maior do que a sugerida por Moritz, portanto, provar limites superlineares só pode ser mais fácil.

Agora, as operações de linha são reversíveis . Segue-se que c (A) pode ser definido equivalentemente como o número mínimo de operações de linha necessárias para produzir A, iniciando na matriz de identidade.

Observe que produzir A dessa maneira gera um circuito aritmético para calcular o mapa levando x para Ax. A fanin de cada porta é 2 e o número de portas que não são de entrada corresponde ao número de operações de linha.

Não há nenhuma redução óbvia na direção reversa (de circuitos para seqüências de operação em linha). Ainda assim, podemos caracterizar c (A) em termos da complexidade do circuito aritmético de Ax em um modelo de circuito restrito: afirmo que c (A) é igual à metade do número mínimo de arestas em um circuito aritmético para A, de fanin no máximo 2 e largura n, onde não cobramos pelas arestas que levam aos portões da fanin 1. (Estou usando a noção usual de largura do circuito aqui.) Isso pode ser mostrado usando a idéia simples esboçada anteriormente.

Agora, aqui está a conexão com problemas bem estudados: tem sido um famoso problema aberto há mais de 30 anos exibir um mapa linear explícito Ax (sobre qualquer campo finito) que requer um número superlinear de portas em um circuito fanin-2. A referência clássica é Valiant, "Argumentos teóricos dos grafos com complexidade de baixo nível", e uma recente pesquisa da Lokam sobre o FTTCS também é útil.

Ao estudar c (A), estamos impondo uma restrição adicional de largura, mas como nossa restrição é tão fraca (largura n), não prevejo que o problema se torne muito mais fácil. Mas ei - eu adoraria provar que estou errado.

Andy Drucker
fonte
2
Além disso, Gowers em seu blog teve uma discussão envolvendo a complexidade da eliminação gaussiana. Eu não li cuidadosamente (é na forma de um longo diálogo), mas pode ser útil: gowers.wordpress.com/2009/11/03/…
Andy Drucker
Apenas para entender isso corretamente, a restrição de largura ocorre porque você tem no máximo n operações por coluna e pode continuar coluna por coluna?
Moritz
Estou pensando em termos de operações de linha. A restrição de largura n corresponde ao fato de termos n linhas em que trabalhar todo o trabalho intermediário. Os n portões do circuito na profundidade t representam os estados das n linhas após t aplicações de operações de linha. (talvez você está dizendo a mesma coisa que me)
Andy Drucker
Se, em vez disso, permitíssemos linhas extras de 'espaço de trabalho auxiliar' em nossa eliminação gaussiana, acredito que obteríamos uma correspondência exata entre a complexidade de reduzir A à identidade e a complexidade do circuito aritmético linear de Ax (que é essencialmente a complexidade cit aritmética, pois multiplicações não ajudam a calcular funções lineares além de um fator constante).
Andy Drucker
Sim, foi o que eu quis dizer. Eu também concordo com a segunda declaração. Um circuito linear geral pode classificar de criar novas linhas sempre que quiser :-)
Moritz
9

Existem referências e são bastante antigas. Eu os encontrei enquanto trabalhava em algoritmos combinatórios para multiplicação de matrizes booleanas.

Em 1966, Moon e Moser provaram que a computação do inverso de uma matriz sobre GF (2) precisa de operações de linha , fornecendo um limite superior e inferior. (Você pode extrair um extra ao trabalhar em um campo finito.)Θ(n2/logn)logn

JW Moon e L. Moser. Um problema de redução de matriz. Matemáticas de Computação 20 (94): 328– 330, 1966.

O artigo deve estar acessível no JSTOR.

Tenho certeza de que o limite inferior é apenas um argumento de contagem, e nenhuma matriz explícita que atinja o limite inferior foi fornecida.

Ryan Williams
fonte