TY - JOUR
AU - Jonathan Buss
AU - Gudmund Frandsen
AU - Jeffery Shallit
PY - 1996/06/03
Y2 - 2020/11/24
TI - The Computational Complexity of Some Problems of Linear Algebra
JF - BRICS Report Series
JA - BRICS
VL - 3
IS - 33
SE - Articles
DO - 10.7146/brics.v3i33.20013
UR - https://tidsskrift.dk/brics/article/view/20013
AB - We consider the computational complexity of some problems dealing with matrix rank. Let E, S be subsets of a commutative ring R.Let x1, x2, ..., xt be variables. Given a matrix M = M(x1, x2, ..., xt)with entries chosen from E union {x1, x2, ..., xt}, we want to determinemaxrankS(M) = max rank M(a1, a2, ... , at)andminrankS(M) = min rank M(a1, a2, ..., at). There are also variants of these problems that specify more about thestructure of M, or instead of asking for the minimum or maximum rank, ask if there is some substitution of the variables that makes the matrix invertible or noninvertible.Depending on E, S, and on which variant is studied, the complexityof these problems can range from polynomial-time solvable to randompolynomial-time solvable to NP-complete to PSPACE-solvable tounsolvable.
ER -