期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：1997
卷号：1997
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：We consider the computational complexity of some problems
dealing with matrix rank. Let E,S be subsets of a
commutative ring R. Let x_1, x_2, ..., x_t be variables.
Given a matrix M = M(x_1, x_2, ..., x_t) with entries
chosen from E union {x_1, x_2, ..., x_t}, we want
to determine maxrank_S (M), i.e. the maximum possible rank
M(a_1, a_2, ..., a_t) can attain when (a_1, a_2, ..., a_t)
are chosen from S^t, and similarly, we want to determine
minrank_S (M), i.e. the minimum possible rank
M(a_1, a_2, ..., a_t) can attain when (a_1, a_2, ..., a_t)
are chosen from S^t. There are also variants of these
problems that specify more about the structure 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 complexity of these problems can range from
polynomial-time solvable to random polynomial-time solvable
to NP-complete to PSPACE-solvable to unsolvable.
