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)

Full work available at URL https://doi.org/10.1007/BF02389894

zbMATH Keywords

algorithminclusion of solutioninterval arithmeticlinear interval equationsNP-hard

Mathematics Subject Classification ID

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

Review text

Let \(A\) be a quadratic interval matrix which is strongly regular and which has rational bounds. It is further assumed that for each \(\delta>0\) there exists a polynomial time algorithm which solves the interval equation \(Ax=b\) for any interval vector \(b\) with rational coefficients within relative or absolute accurracy \(\delta\). Then it is shown that \(P=NP\). This result holds also under the additional restriction that \(A\) is symmetric.

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

• Approximate linear algebra is intractable
• Computing Exact Componentwise Bounds on Solutions of Lineary Systems with Interval Data is NP-Hard
• 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?)
• Interval linear systems with symmetric matrices, skew-symmetric matrices and dependencies in the right hand side
• Interval Methods for Systems of Equations
• On the Symmetric and Unsymmetric Solution Set of Interval Systems

Cited in

(7)

• Optimal enclosure of quadratic interval functions
• 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?)
• scientific article; zbMATH DE number 869739 (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)