ECCC-Report TR96-024https://eccc.weizmann.ac.il/report/1996/024Comments and Revisions published for TR96-024en-usFri, 22 Mar 1996 14:19:52 +0300
Paper TR96-024
| The complexity of matrix rank and feasible systems of linear equations |
Eric Allender,
Robert Beals,
Mitsunori Ogihara
https://eccc.weizmann.ac.il/report/1996/024We 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 NC^1-reducibility,
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.
Fri, 22 Mar 1996 14:19:52 +0300https://eccc.weizmann.ac.il/report/1996/024