Complexity of some linear problems with interval data.

*(English)*Zbl 0888.65052Various 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)

##### 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 |