Range Estimation Is NP-Hard for ε~2 Accuracy and Feasible for ε~(2-δ)

摘要

The basic problem of interval computations is: given a function f(x_1,...,x_n) and n intervals [x_i, (x~-)_i], find the (interval) range y of the given function on the given intervals. It is known that even for quadratic polynomials f(x_1, ...,x_n), this problem is NP-hard. In this paper, following the advice of A. Neumaier, we analyze the complexity of asymptotic range estimation, when the bound ε on the width of the input intervals tends to 0. We show that for small c > 0, if we want to compute the range with an accuracy c· ε~2, then the problem is still NP-hard; on the other hand, for every δ > 0, there exists a feasible algorithm which asymptotically, estimates the range with an accuracy c·ε~(2-δ).