Loading...
Please wait, while we are loading the content...
Similar Documents
Computational Complexity and Feasibility of Data Processing and Interval Computations, with Extension to Cases When We Have Partial Information about Probabilities
| Content Provider | Semantic Scholar |
|---|---|
| Author | Kreinovich, Vladik Longpré, Luc |
| Copyright Year | 2003 |
| Abstract | In many real-life situations, we are interested in the value of a physical quantity y that is diicult or impossible to measure directly. To estimate y, we nd some easier-to-measure quantities x 1 ; : : : ; x n which are related to y by a known relation y = f (x 1 ; : : : ; x n). Measurements are never 100% accurate; hence, the measured values e x i are diierent from x i , and the resulting estimate e y = f (e x 1 ; : : : ; e x n) is diierent from the desired value y = f (x 1 ; : : : ; x n). How diierent? Traditional engineering to error estimation in data processing assumes that we know the probabilities of diierent measurement error x i def = e x i ? x i. In many practical situations, we only know the upper bound 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 def = e x i ? i ; e x i + i ]. In this case, it is important to nd the range y of all possible values of y = f (x 1 ; : : : ; x n) when x i 2 x i. We start the paper with a brief overview of the computational complexity of the corresponding interval computation problems. We then discuss how this computational complexity changes when, in addition to the upper bounds i , we have some partial information about the probabilities of diierent values of x i. We also show how the use of quantum computing can speed up some computations related to interval and probabilistic uncertainty. Most of the related problems turn out to be, in general, at least NP-hard. We end the paper with speculations on whether (and how) hypothetic physical devices can compute NP-hard problems faster than in exponential time. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://digitalcommons.utep.edu/cgi/viewcontent.cgi?article=1388&context=cs_techrep |
| Alternate Webpage(s) | http://www.cs.utep.edu/vladik/2003/tr03-22.ps.gz |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
