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 arithmeticlinear interval systemsNP-hard

Mathematics Subject Classification ID

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

Review text

The complexity of the solution of linear interval systems is considered with special attention to computer arithmetic.

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)

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