Approximate linear algebra is intractable

DOI10.1016/S0024-3795(94)00026-3zbMath0846.65015MaRDI QIDQ1906787

S. I. Noskov, Vladik Ya. Kreinovich, Anatoly V. Lakeyev

Publication date: 7 March 1996

Published in: Linear Algebra and its Applications (Search for Journal in Brave)

zbMATH Keywords

perturbationNP-hardoptimal solutioncomplexity analysisimprecise linear systems

Mathematics Subject Classification ID

Related Items (3)

Why it is computationally harder to reconstruct the past than to predict the future ⋮ PC-SOLUTION AND QUASI-SOLUTION OF THE INTERVAL INPUT-OUTPUT BALANCE MODEL ⋮ Linear interval equations: Computing enclosures with bounded relative or absolute overestimation is NP-hard

Cites Work

• Systems of linear interval equations
• Derived eigenvalues of symmetric matrices, with applications to distance geometry
• Identification and application of bounded-parameter models
• On the value of information in system identification-bounded noise case
• Die Überschätzung des Wertebereichs einer Funktion in der Intervallrechnung mit Anwendungen auf lineare Gleichungssysteme
• Checking robust nonsingularity is NP-hard
• Über Struktur und Abschätzungen der Lösungsmenge von linearen Gleichungssystemen mit Intervallkoeffizienten
• Optimal sampling schedule for parameter estimation of linear models with unknown but bounded measurement errors
• On the Solution Set of a Linear System with Inaccurate Coefficients
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Approximate linear algebra is intractable