×

Error estimation for indirect measurements: Interval computation problem is (slightly) harder than a similar probabilistic computational problem. (English) Zbl 0942.65047

The authors study the complexity of probabilistic computational problems related to indirect measurements whenever the estimate function is: a) a polynomial; b) a rational function. In case a) the existence of a polynomial time algorithm is demonstrated, whereas in case b) NP-hardness established.
Reviewer: S.Markov (Sofia)

MSC:

65G30 Interval and finite arithmetic
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
65Y20 Complexity and performance of numerical algorithms
PDFBibTeX XMLCite
Full Text: DOI