Komplexität der Lösung linearer Gleichungen

Was ist über die Komplexität der Lösung eines linearen Gleichungssystems über ein endliches Feld bekannt? Ich weiß, dass es einen -Algorithmus (Gauß) gibt, der eine Lösung berechnet, und dass es für spärliche Systeme noch bessere Algorithmen gibt. Ich habe mich jedoch gefragt, ob es eine komlexitätstheoretische Charakterisierung dieses Problems gibt. Ist zum Beispiel das entsprechende Entscheidungsproblem in N C ? Ist es für jede Komplexitätsklasse vollständig?$O(n^3)$$\mathbf{NC}$

Ich bin mir nicht sicher, ob dies eine Frage auf Forschungsebene ist, aber das Lösen linearer Systeme über ist ein M o d p L- vollständiges Problem, daher ist es insbesondere in N C 2 . Allgemeiner kann die lineare Algebra über F p k (zumindest für k fest) auf den Fall F p reduziert werden.$\mathbb F_p$$\mathrm{Mod}_p\mathrm L$$\mathrm{NC}^2$$\mathbb F_{p^k}$$k$$\mathbb F_p$

$\mathbb F_2$$O(n^\omega)$$\omega$

Verweise:

Ibarra, O., Moran, S. und Hui, R. 1982. Eine Verallgemeinerung des schnellen LUP-Matrixzerlegungsalgorithmus und seiner Anwendungen . Journal of Algorithms 3, 45 {56.

Jeannerod, C.-P. , Pernet, C. und Storjohann, A. 2011. Rangprofil, das die Gaußain-Eliminierung und die CUP-Matrixzerlegung zeigt .