NP-hard classes of linear algebraic systems with uncertainties (Q1362824)

This paper considers `linear equations' \((m\) equations, \(n\) unknowns), where the matrix entries as well as the right hand side entries may depend on several parameters. One question is to decide whether such a system admits a solution for at least one parameter configuration. The authors show that this -- and similar -- problems are ordinarily NP-hard, even if one restricts the class of `linear equations' to smaller subclasses like interval matrices or positive interval matrices.