Is It Possible to Have a Feasible Enclosure-Computing Method Which Is Independent of the Equivalent Form?
Marcin Michalak, Владик Крейнович · scholarworks - UTEP (The University of Texas at El Paso) · 2013
The problem of computing the range y of a given function f(x1,..., xn) over given intervals xi – often called the main problem of interval computations – is, in general, NP-hard. This means that unless P = NP, it is not possible to have a feasible ( = polynomial time) algorithm that always computes the desired range. Instead, interval computations algorithms compute an enclosure Y ⊇ y for the desired range. For all known feasible enclosure-computing methods – starting with straightforward interval computations – there exist two expressions f(x1,..., xn) and g(x1,..., xn) for computing the same function that lead to different enclosures. We prove that, unless P = NP, this is inevitable: it is not possible to have a feasible enclosure-computing method which is independent of the equivalent form. Keywords: interval computations, enclosure, equivalent form, NP-hard