Rohn, Jiří Complexity of some linear problems with interval data. (English) Zbl 0888.65052 Reliab. Comput. 3, No. 3, 315-323 (1997). 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. Reviewer: H.Ratschek (Düsseldorf) Cited in 11 Documents MSC: 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 Keywords:complexity; interval arithmetic; systems of linear equations or inequalities; linear or quadratic optimization; polynomial time; NP-hard Software:mctoolbox PDFBibTeX XMLCite \textit{J. Rohn}, Reliab. Comput. 3, No. 3, 315--323 (1997; Zbl 0888.65052) Full Text: DOI