zbMATH — the first resource for mathematics

Complexity of some linear problems with interval data. (English) Zbl 0888.65052
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.

65F30 Other matrix algorithms (MSC2010)
65Y20 Complexity and performance of numerical algorithms
65K05 Numerical mathematical programming methods
90C05 Linear programming
90C20 Quadratic programming
65G30 Interval and finite arithmetic
65F05 Direct numerical methods for linear systems and matrix inversion
Full Text: DOI