Classe de complexidade da inversão de matriz

Está invertendo uma matriz na classe Complexidade ?$\text{P}$

Desde o tempo de execução, eu diria que sim $\mathcal{O}(n^3)$ mas a matriz invertida pode conter entradas em que o tamanho não é polinomialmente limitado pela entrada?

Sim, isso pode ser feito em tempo polinomial, mas a prova é bastante sutil. Não é simplesmente$O(n^3)$tempo, porque a eliminação gaussiana envolve multiplicar e adicionar números, e o tempo para executar cada uma dessas operações aritméticas depende de quão grandes elas são. Para algumas matrizes, os valores intermediários podem se tornar extremamente grandes, de modo que a eliminação gaussiana não é necessariamente executada no tempo polinomial.

Felizmente, não são algoritmos que não são executados em tempo polinomial. Eles exigem muito mais cuidado no design do algoritmo e na análise do algoritmo para provar que o tempo de execução é polinomial, mas isso pode ser feito. Por exemplo, o tempo de execução do algoritmo de Bareiss é algo como$O(n^5 (\log n)^2)$ [na verdade, é mais complexo que isso, mas tome isso como uma simplificação por enquanto].

Para muito mais detalhes, consulte a entrada de blog de Dick Lipton, Forgetting Results, e Qual é a complexidade de tempo real da eliminação gaussiana? e resumo da Wikipedia .

Finalmente, uma palavra de cautela. O tempo de execução preciso depende exatamente de qual campo você está trabalhando. A discussão acima se aplica se você estiver trabalhando com números racionais. Por outro lado, se, por exemplo, você estiver trabalhando no campo finito$GF(2)$(os inteiros módulo 2), seguida de eliminação de Gauss ingênuo não ser executado em$O(n^3)$Tempo. Se você não entender o que isso significa, provavelmente poderá ignorar este último parágrafo.

Existe uma fórmula para as entradas da matriz inversa que fornece cada entrada como uma razão de dois determinantes, um de menor da matriz original e o outro de toda a matriz original. Isso deve ajudá-lo a limitar o tamanho das entradas na matriz inversa, se você for cuidadoso, dada uma noção razoável de "tamanho" (observe que, mesmo que você comece com uma matriz inteira, o inverso pode conter entradas racionais).

Dito isto, muitas vezes a matriz inversa é estudada do ponto de vista da teoria da complexidade algébrica, na qual você conta operações básicas independentemente da magnitude. Nesse modelo, pode-se mostrar que a complexidade da matriz inversa é equivalente à complexidade da multiplicação da matriz, até termos polilogarítmicos; talvez essa redução também possa ajudá-lo a limitar o tamanho dos coeficientes.

Dado o algoritmo eficiente no modelo da teoria da complexidade algébrica, questiona-se se isso implica um algoritmo igualmente eficiente no modelo usual; pode ser que, embora as entradas finais sejam de tamanho polinomial, o cálculo envolva outras maiores? Provavelmente não é esse o caso, e mesmo que fosse, talvez o problema pudesse ser evitado usando o teorema chinês restante.