Intervals and their Applications

Vladik Kreinovich
University of Texas at El Paso

Why do we need computers? 

One of the main reasons for them is that 
in many real-life problems, we are interested in the 
value of the physical quantity y that is difficult or even 
impossible to measure directly: e.g., the amount of oil in the well, or 
the distance to the galaxies. In such cases, we measure some other 
quantities xi that are in a known way connected with y (i.e., for which 
y=f(x1,...,xn)), and then use the results Xi of these 
measurements to compute the estimate Y=f(X1,...,Xn) for y. The 
corresponding data processing algorithm f can be very time-intensive, 
that is why we need computers to perform these computations.

The following problem is often overlooked in computing, 
but is of great importance in practice: 
Measurements are never absolutely precise, so there can be 
measurement errors; we usually know the guaranteed accuracy
Di of each measurement. As a result, the only information that 
we have about the actual (unknown) value of xi is that xi 
belongs to the interval [xi]=[Xi-Di,Xi+Di]. 
We also know the algorithm f that transforms 
the values xi into the value of the desired quantity y. We want
to know the interval of possible values of y. 

Computations that
solve this problem are called interval computations. 

In 1981, it was proven that even for polynomial functions f, 
the problem of computing the range Y exactly 
is computationally intractable (NP-hard).

In this talk, we describe heuristic techniques that provide 
reasonably good estimates for the desired range, and show how these 
techniques can be used to solve optimization problems and other 
decision problems. 

We also describe what happens if, in addition to the upper bound D on 
the measurement error X-x, we also have some additional information about 
the probabilities of different values of this error.