TR96-024 Authors: Eric Allender, Robert Beals, Mitsunori Ogihara

Publication: 22nd March 1996 14:19

Downloads: 1512

Keywords:

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.