×

On a refined analysis of some problems in interval arithmetic using real number complexity theory. (English) Zbl 1055.65061

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.

MSC:

65G30 Interval and finite arithmetic
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI