COMPUTING EXACT COMPONENTWISE BOUNDS ON SOLUTIONS OF LINEAR-SYSTEMS WITH INTERVAL DATA IS NP-HARD

Authors
ROHN J KREINOVICH V
Citation
J. Rohn et V. Kreinovich, COMPUTING EXACT COMPONENTWISE BOUNDS ON SOLUTIONS OF LINEAR-SYSTEMS WITH INTERVAL DATA IS NP-HARD, SIAM journal on matrix analysis and applications, 16(2), 1995, pp. 415-420
Citations number
12
Categorie Soggetti
Mathematics,Mathematics
Journal title
SIAM journal on matrix analysis and applications → ACNP
ISSN journal
08954798
Volume
16
Issue
2
Year of publication
1995
Pages
415 - 420
Database
ISI
SICI code
0895-4798(1995)16:2<415:CECBOS>2.0.ZU;2-E
Abstract
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 giv en linear system with a nonsingular matrix by perturbing all the data independently of each other within prescribed tolerances.