Computational Complexity and Feasibility of Data Processing and Interval Computations, with Extension to Cases When We Have Partial Information about Probabilities
Владик Крейнович, Luc Longpré · scholarworks - UTEP (The University of Texas at El Paso) · 2003
In many real-life situations, we are interested in the value of a physical quantity y that is difficult or impossible to measure directly. To estimate y, we find some easier-to-measure quantities x 1 ; : : : ; xn which are related to y by a known relation y = f(x 1 ; : : : ; xn ). Measurements are never 100% accurate; hence, the measured values e x i are different from x i , and the resulting estimate e y = f(ex 1 ; : : : ; e xn ) is different from the desired value y = f(x 1 ; : : : ; xn ). How different? Traditional engineering to error estimation in data processing assumes that we know the probabilities of different measurement error \\Deltax i = e x i \\Gamma x i . In many practical situations, we only know the upper bound \\Delta i for this error; hence, after the measurement, the only information that we have about x i is that it belongs to the interval x i = [ex i \\Gamma \\Delta i ; e x i + \\Delta i ]. In this case, it is important to find the range y of all possible values of y = f(x 1 ; : : : ; xn ) when x i 2 x i . We start the paper with a brief overview of the computational complexity of the corresponding interval computation problems.