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

DOI10.1007/BF02389894zbMATH Open0871.65022MaRDI QIDQ676167FDOQ676167

Authors: Vladik Kreinovich, A. V. Lakeyev 

Publication date: 1 October 1997

Published in: Reliable Computing (Search for Journal in Brave)

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

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)

Cites Work

• Title not available (Why is that?)
• Interval Methods for Systems of Equations
• Title not available (Why is that?)
• Interval linear systems with symmetric matrices, skew-symmetric matrices and dependencies in the right hand side
• Computing Exact Componentwise Bounds on Solutions of Lineary Systems with Interval Data is NP-Hard
• On the Symmetric and Unsymmetric Solution Set of Interval Systems
• Approximate linear algebra is intractable
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (5)

• Solving linear interval systems is NP-hard even if we exclude overflow and underflow
• Interval mathematics, algebraic equations and optimization
• Enclosing solutions of linear interval equations is NP-hard
• Title not available (Why is that?)
• 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)