Approximate linear algebra is intractable (Q1906787)

The authors consider imprecise linear systems \(Ax= b\), where the perturbation of the system matrix \(A\) and the right-hand side \(b\) can be represented in the form \(A= A^{(0)}+ \sum p_\mu A^{(\mu)}\) and \(b= b^{(0)}+ \sum q_\mu b^{(\mu)}\), respectively, with unknown coefficients \(p_\mu\) and \(q_\mu\) satisfying one of following five relations: \(|p|_x\leq \alpha\) and \(|q|_y\leq \beta\) with \(x, y\in \{2, \infty\}\), or \(|(p, q)|_2\leq \alpha\). The authors prove that the problems of checking whether the system is consistent (Theorem 1), of computing a \(\delta\)-approximate to the optimal solution of a nonsingular imprecise linear system (Theorem 2), and, therefore, of computing the optimal solution of a nonsingular imprecise linear system (Corollary) are NP-hard in any of the five versions of measuring the perturbation.