University of Texas at El Paso
Departmental Technical Reports (CS)
2011
Enclosure
Articles 1 - 1 of 1
Full-Text Articles in Computer Engineering
Is It Possible To Have A Feasible Enclosure-Computing Method Which Is Independent Of The Equivalent Form?, Marcin Michalak, Vladik Kreinovich
Jun 2011
Is It Possible To Have A Feasible Enclosure-Computing Method Which Is Independent Of The Equivalent Form?, Marcin Michalak, Vladik Kreinovich
Departmental Technical Reports (CS)
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] 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 …