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

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.