Complexidade da resolução de equações lineares

9

O que se sabe sobre a complexidade de resolver um sistema de equações lineares sobre algum campo finito? Eu sei que existe um algoritmo (Gauss) que calcula uma solução e que para sistemas esparsos existem algoritmos ainda melhores. No entanto, eu queria saber se havia alguma caracterização teórica da comlexidade desse problema. Por exemplo, o problema de decisão correspondente em ? Está completo para qualquer classe de complexidade?O(n3)NC

Alan
fonte

Respostas:

11

Não tenho a certeza esta é uma questão de nível de investigação, no entanto, resolver sistemas lineares mais de é um H O d p L -completo problema, portanto, em particular, é em N C 2 . De um modo mais geral, a álgebra linear sobre F p k (pelo menos para k fixo) pode ser reduzida ao caso F p .FpModpeuNC2FpkkFp

Emil Jeřábek
fonte
6

Um resultado conhecido há mais de 30 anos é que a Eliminação Guassiana sobre pode ser feita por várias decomposições que levam O ( n ω ) , onde ω é a constante de multiplicação da matriz.F2O(nω)ω

Referências:

Ibarra, O., Moran, S. e Hui, R. 1982. Uma generalização do algoritmo de decomposição da matriz LUP rápida e aplicações . Journal of Algorithms 3, 45 {56.

Jeannerod, C.‑P. , Pernet, C. e Storjohann, A. 2011. Perfil de classificação que revela a eliminação de Gaussain e a decomposição da matriz CUP .

RB
fonte