×

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].

MSC:

65F30 Other matrix algorithms (MSC2010)
65G30 Interval and finite arithmetic
65Y20 Complexity and performance of numerical algorithms
PDFBibTeX XMLCite