Estimating the Range of a Polynomial Over Interval with Relative Accuracy ε is NP-hard for ε ≤ 1 and Feasible for ε > 1
V. Kreinovich, Sergey P. Shary · Numerical Analysis and Applications · 2025
In many practical situations, we need to compute an enclosure for the range of a polynomial in several variables $$f({{x}_{1}}, \ldots ,{{x}_{n}})$$ on given intervals $$[{{\underline x }_{1}},{{\bar {x}}_{1}}]$$ , …, $$[{{\underline x }_{n}},{{\bar {x}}_{n}}]$$ with a certain relative accuracy $$\varepsilon > 0$$ . It was known that this problem is NP-hard for all $$\varepsilon 1$$ .