Rohn, Jiří Linear interval equations: Computing enclosures with bounded relative overestimation is NP-hard. (English) Zbl 0841.65027 Kearfott, R. Baker (ed.) et al., Applications of interval computations. Proceedings of an international workshop, El Paso, TX, USA, February 23-25, 1995. Dordrecht: Kluwer Academic Publishers. Appl. Optim. 3, 81-89 (1996). Summary: It is proved that if there exists a polynomial-time algorithm for enclosing solutions of linear interval equations with relative overestimation better than \({4\over n^2}\) (where \(n\) is the number of equations), then \(P = NP\). The result holds for the symmetric case as well.For the entire collection see [Zbl 0836.00038]. Cited in 2 Documents MSC: 65F30 Other matrix algorithms (MSC2010) 65G30 Interval and finite arithmetic 65Y20 Complexity and performance of numerical algorithms Keywords:bounded relative overestimation; NP-hard; enclosure; polynomial-time algorithm; linear interval equations PDFBibTeX XMLCite \textit{J. Rohn}, Appl. Optim. 3, 81--89 (1996; Zbl 0841.65027)