Solving linear interval systems is NP-hard even if we exclude overflow and underflow

DOI10.1023/A:1024423917616MaRDI QIDQ1276134zbMATH OpenOpenAlexFDO

Authors G. Heindl, A. V. Lakeyev, Vladik Kreinovich

Publication date 9 September 1999

Published in Reliable Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1023/a:1024423917616

zbMATH Keywords

complexityinterval arithmeticNP-hardlinear interval systems

Mathematics Subject Classification ID

Direct numerical methods for linear systems and matrix inversion (65F05) Complexity and performance of numerical algorithms (65Y20) Interval and finite arithmetic (65G30)

Recommendations

• scientific article; zbMATH DE number 804135
• 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
• Linear interval equations: Computing enclosures with bounded relative or absolute overestimation is NP-hard
• scientific article; zbMATH DE number 869739
• scientific article; zbMATH DE number 714524
• Solving overdetermined systems of interval linear equations
• NP-hardness of approximately solving linear equations over reals
• On the solution of interval linear systems

Cited in

(4)

• Extension of the Hansen-Bliek method to right-quantified linear systems
• scientific article; zbMATH DE number 7406258 (Why is no real title available?)
• Solving the linear interval tolerance problem for weight initialization of neural networks
• scientific article; zbMATH DE number 804135 (Why is no real title available?)

This page was built for publication: Solving linear interval systems is NP-hard even if we exclude overflow and underflow

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