The Computational Complexity of Some Problems of Linear Algebra

摘要: We consider the computational complexity of some problems dealing with matrix rank. Let E, S be subsets a commutative ring R. x1, x2, ?, xt variables. Given M=M(x1, xt) entries chosen from E?{x1, xt}, we want to determine maxrankS(M)=max(a1, a2, at)?St rank M(a1, at) and minrankS(M)=min(a1, at). There are also variants these that specify more about structure M, or instead asking for minimum maximum rank, they ask if there is substitution variables makes invertible noninvertible. Depending on S, which variant studied, can range polynomial-time solvable random NP-complete PSPACE-solvable unsolvable. An approximation version minrank problem shown MAXSNP-hard.