On a refined analysis of some problems in interval arithmetic using real number complexity theory
From MaRDI portal
Publication:1826441
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.
Recommendations
- Mathematical Foundations of Computer Science 2003
- Computation complexity of the range of a polynomial in several variables
- Range estimation is NP-hard for \({\varepsilon}^{2}\) accuracy and feasible for \({\varepsilon}^{2-\delta}\)
- Complexity of some linear problems with interval data
- scientific article; zbMATH DE number 869739
Cited in
(7)- Optimal enclosure of quadratic interval functions
- Range estimation is NP-hard for \({\varepsilon}^{2}\) accuracy and feasible for \({\varepsilon}^{2-\delta}\)
- A bright side of NP-hardness of interval computations: Interval heuristics applied to NP-problems
- scientific article; zbMATH DE number 1346365 (Why is no real title available?)
- Mathematical Foundations of Computer Science 2003
- Complexity aspects of a semi-infinite optimization problem†
- Grey dynamic input-output analysis
This page was built for publication: On a refined analysis of some problems in interval arithmetic using real number complexity theory
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1826441)
