On a refined analysis of some problems in interval arithmetic using real number complexity theory (Q1826441)

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.