Computing Exact Componentwise Bounds on Solutions of Lineary Systems with Interval Data is NP-Hard
Jǐŕı Rohn, Владик Крейнович · SIAM Journal on Matrix Analysis and Applications · 1995
We prove that it is NP-hard to compute the exact componentwise bounds on solutions of all the linear systems that can be obtained from a given linear system with a nonsingular matrix by perturbing all the data independently of each other within prescribed tolerances.