Meer, Klaus On a refined analysis of some problems in interval arithmetic using real number complexity theory. (English) Zbl 1055.65061 Reliab. Comput. 10, No. 3, 209-225 (2004). The author starts from the well-known fact that the best linear interval approximation of a quadratic function is \(NP\)-hard. If, however, the problem is considered in the real number model it “most likely” does not face any longer the difficulty of \(NP_{\mathbb{R}}\). Hence, the above-mentioned problem is not \(NP_{\mathbb{R}}\)-hard under so-called weak polynomial time reductions and is “likely” not \(NP_{\mathbb{R}}\)-hard under polynomial time reductions. Reviewer: H. Ratschek (Düsseldorf) Cited in 2 Documents MSC: 65G30 Interval and finite arithmetic 68Q25 Analysis of algorithms and problem complexity Keywords:best linear interval approximation; quadratic function; NP-hard; polynomial time reductions PDFBibTeX XMLCite \textit{K. Meer}, Reliab. Comput. 10, No. 3, 209--225 (2004; Zbl 1055.65061) Full Text: DOI