期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：1996
卷号：1996
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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 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.
