Enclosing solutions of linear interval equations is NP-hard
From MaRDI portal
Publication:1340883
DOI10.1007/BF02307386zbMath0809.65019OpenAlexW152607821MaRDI QIDQ1340883
Publication date: 20 December 1994
Published in: Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf02307386
polynomial-time algorithmlinear interval equationsenclosure methodNP-hardnesssolution set of interval systems
Interval and finite arithmetic (65G30) Direct numerical methods for linear systems and matrix inversion (65F05) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Linear equations (linear algebraic aspects) (15A06)
Related Items
Checking bounds on solutions of linear interval equations is NP-hard, The interval Lyapunov matrix equation: analytical results and an efficient numerical technique for outer estimation of the united solution set, Results concerning interval linear systems with multiple right-hand sides and the interval matrix equation \(AX=B\), On the optimal solution set in interval linear programming, Complexity aspects of a semi-infinite optimization problem†, Calculation of exact bounds for the solution set of linear interval systems
Cites Work
