Linear interval equations: Computing enclosures with bounded relative or absolute overestimation is NP-hard

DOI10.1007/BF02389894MaRDI QIDQ676167zbMATH OpenFDO

Authors Vladik Kreinovich, A. V. Lakeyev

Publication date 1 October 1997

Published in Reliable Computing (Search for Journal in Brave)

zbMATH Keywords

algorithminterval arithmeticNP-hardlinear interval equationsinclusion of solution

Mathematics Subject Classification ID

Complexity and performance of numerical algorithms (65Y20) Iterative numerical methods for linear systems (65F10) Interval and finite arithmetic (65G30)

Recommendations

• scientific article; zbMATH DE number 869739
• Enclosing solutions of linear interval equations is NP-hard
• Checking bounds on solutions of linear interval equations is NP-hard
• Computing Exact Componentwise Bounds on Solutions of Lineary Systems with Interval Data is NP-Hard

Cites work

• scientific article; zbMATH DE number 3880009 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 804135 (Why is no real title available?)
• scientific article; zbMATH DE number 869739 (Why is no real title available?)
• Approximate linear algebra is intractable
• Computing Exact Componentwise Bounds on Solutions of Lineary Systems with Interval Data is NP-Hard
• Interval Methods for Systems of Equations
• Interval linear systems with symmetric matrices, skew-symmetric matrices and dependencies in the right hand side
• On the Symmetric and Unsymmetric Solution Set of Interval Systems

Cited in

(5)

• Solving linear interval systems is NP-hard even if we exclude overflow and underflow
• Enclosing solutions of linear interval equations is NP-hard
• Interval mathematics, algebraic equations and optimization
• scientific article; zbMATH DE number 733109 (Why is no real title available?)
• Calculation of exact bounds for the solution set of linear interval systems

This page was built for publication: Linear interval equations: Computing enclosures with bounded relative or absolute overestimation is NP-hard

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q676167)