TY - GEN

T1 - The complexity of matrix rank and feasible systems of linear equations

AU - Allender, Eric

AU - Beals, Robert

AU - Ogihara, Mitsunori

N1 - Funding Information:
l Department of Computer Science, Rutgers 1179, Piscataway, NJ 08855-1179, allender@cs. ported in part by NSF grant CC! R-9509603. tDIMACS, Rutgers University, PO 1179, 08855-1179, and School for Mathematics, Institute Study, Olden Princeton, NJ 08540, rbeals@dinacs Supported in by an NSF Mathematical Sciences Fellowship. ~DePartment Rochester, NY, 14627, ogihara@cs.
Publisher Copyright:
© 1996 ACM.

PY - 1996/7/1

Y1 - 1996/7/1

N2 - We characterize the complexity of some natural and important problems in linear algebra. In particular, we identify natural complexity classes for which the problems of (a) determining if a system of linear equations is feasible and (b) computing the rank of an integer matrix, (as well as other problems), are complete under logspace reductions. As an important part of presenting this classification, we show that the "exact counting logspace hierarchy" collapses to near the bottom level. (We review the definition of this hierarchy below.) We further show that this class is closed under NC1-reducibihty, and that it consists of exactly those languages that have logspace uniform span programs (introduced by Karchmer and Wigderson) over the rationals. In addition, we contrast the complexity of these problems with the complexity of determining if a system of linear equations has an integer solution.

AB - We characterize the complexity of some natural and important problems in linear algebra. In particular, we identify natural complexity classes for which the problems of (a) determining if a system of linear equations is feasible and (b) computing the rank of an integer matrix, (as well as other problems), are complete under logspace reductions. As an important part of presenting this classification, we show that the "exact counting logspace hierarchy" collapses to near the bottom level. (We review the definition of this hierarchy below.) We further show that this class is closed under NC1-reducibihty, and that it consists of exactly those languages that have logspace uniform span programs (introduced by Karchmer and Wigderson) over the rationals. In addition, we contrast the complexity of these problems with the complexity of determining if a system of linear equations has an integer solution.

UR - http://www.scopus.com/inward/record.url?scp=0029723580&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0029723580&partnerID=8YFLogxK

U2 - 10.1145/237814.237856

DO - 10.1145/237814.237856

M3 - Conference contribution

AN - SCOPUS:0029723580

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 161

EP - 167

BT - Proceedings of the 28th Annual ACM Symposium on Theory of Computing, STOC 1996

PB - Association for Computing Machinery

T2 - 28th Annual ACM Symposium on Theory of Computing, STOC 1996

Y2 - 22 May 1996 through 24 May 1996

ER -