¿Qué se sabe sobre la complejidad de resolver un sistema de ecuaciones lineales sobre un campo finito? Sé que existe un algoritmo (Gauss) que calcula una solución y que para sistemas dispersos hay algoritmos aún mejores. Sin embargo, me preguntaba si había alguna caracterización teórica de la complejidad de este problema. Por ejemplo, ¿está el problema de decisión correspondiente en ? ¿Está completo para cualquier clase de complejidad?
No estoy seguro de que esta sea una pregunta de nivel de investigación, sin embargo, resolver sistemas lineales sobre es un problema completo de , por lo tanto, en particular, está en . En términos más generales, el álgebra lineal sobre (al menos para fijo) puede reducirse al caso .
Un resultado conocido por más de 30 años es que la eliminación de Guassian sobre se puede realizar mediante varias descomposiciones que toman O ( n ω ) , donde ω es la constante de multiplicación de la matriz.
Referencias
Ibarra, O., Moran, S. y Hui, R. 1982. Una generalización del algoritmo de descomposición rápida de la matriz LUP y sus aplicaciones . Diario de Algoritmos 3, 45 {56.
Jeannerod, C.-P. , Pernet, C. y Storjohann, A. 2011. Perfil de clasificación que revela la eliminación de Gaussain y la descomposición de la matriz CUP .