Complexity of some linear problems with interval data (Q1371175)

Various problems are considered which are connected with solving systems of linear equations or inequalities or solving linear or quadratic optimization problems. I.e., it is investigated which of these problems can be solved in polynomial time or are NP-hard when the coefficients of the systems are allowed to be inexact and to range over compact intervals. It is interesting to learn that many of the addressed investigations can be reduced to the fact that it is NP-hard to decide whether \(|A|\geq 1\) for a real matrix \(A\) is satisfied, where the matrix norm used is subordinate to the maximum norm and the 1-norm of vectors.