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 ∪ {x_1, x_2, ..., x_t}, we want to determine maxrank_s(M) = max_[(a-1,a_2, ...,a_t)∈S~t] rank M(a_1, a_2, ..., a_t) and minrank_s(M) = min_[(a_1,a_2, ... , a-t)∈ S~t rank M(a_1, a_2, ..., a_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, they ask if there is some substitution of the variables that makes the matrix invertible or noninvertible. Depending on E, S, and which variant is studied, the complexity of these problems cam range from plynomial-time solvable to random polynomial-time solvable to NP-complete to PSPACE-aolvable to unsolvable. An approximation version of the minrank problem is shown to be MAXSNP-hard.
展开▼
机译：我们考虑一些处理矩阵秩的问题的计算复杂性。令E，S为交换环R的子集。令x_1，x_2，...，x_t为变量。给定矩阵M = M（x_1，x_2，...，x_t）并从E∪{x_1，x_2，...，x_t}中选择条目，我们要确定maxrank_s（M）= max _ [（（a-1 ，a_2，...，a_t）∈S〜t]秩M（a_1，a_2，...，a_t）和minrank_s（M）= min _ [（（a_1，a_2，...，at））∈S〜t等级M（a_1，a_2，...，a_t）。这些问题也有一些变体，它们详细说明了M的结构，或者询问是否存在使矩阵可逆或不可逆的变量的替代，而不是要求最小或最大秩。取决于E，S以及研究的变量，这些问题的复杂性范围从多项式时间可解决到随机多项式时间可解决到NP完全到PSPACE可解决到不可解决。 Minrank问题的近似版本显示为MAXSNP-hard。
展开▼
