Estimating the range of a polynomial on an interval with relative accuracy $\varepsilon$ is NP-hard for $\varepsilon\leqslant 1$ and feasible for $\varepsilon> 1$

In many practical situations, we need to compute an enclosure for the range of a polynomial in several variables $f(x_1,\dots,x_n)$ on given intervals $[\underline{x}_1,\overline{x}_1],\dots,[\underline{x}_n,\overline{x}_n]$ with a certain relative accuracy $\varepsilon>0$. It was known that this problem is NP-hard for all $\varepsilon<1/8$ but it was not known whether the problem is NP-hard for the other values of $\varepsilon$. Our article provides an almost complete answer to this question, namely, we prove that the problem under study is NP-hard for all $\varepsilon\leqslant 1$ and feasible (polynomially complex) for all $\varepsilon>1$.