Abstract
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{\text{/}}8\) , but it was not known whether the problem is NP-hard for other values \(\varepsilon \) . Our article provides a 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\) .
