The complexity of matrix rank and feasible systems of linear equations

DOI10.1007/s000370050023zbMath0949.68071MaRDI QIDQ1961056

Eric W. Allender, Robert Beals, Ogihara, Mitsunori

Publication date: 5 December 2000

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s000370050023

zbMATH Keywords

natural complexity classes

Mathematics Subject Classification ID

68W30: Symbolic computation and algebraic computation

15A99: Basic linear algebra

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

Related Items

ON THE MINIMAL POLYNOMIAL OF A MATRIX, Parameterised counting in logspace, Space Hardness of Solving Structured Linear Systems., The parallel complexity of graph canonization under abelian group action, The orbit problem is in the GapL hierarchy, Counting classes and the fine structure between \(\mathrm{NC}^1\) and \(L\), The complexity of the characteristic and the minimal polynomial., Computing the sign or the value of the determinant of an integer matrix, a complexity survey., A note on closure properties of logspace MOD classes, Evaluation of circuits over nilpotent and polycyclic groups, On the complexity of noncommutative polynomial factorization, On the power of unambiguity in log-space, Towards a tight hardness-randomness connection between permanent and arithmetic circuit identity testing, On the complexity of matrix rank and rigidity, Monomials in arithmetic circuits: complete problems in the counting hierarchy, Monomials, multilinearity and identity testing in simple read-restricted circuits, Bounded Treewidth and Space-Efficient Linear Algebra, Evaluating Matrix Circuits, The Orbit Problem Is in the GapL Hierarchy