Kosheleva, Olga; Kreinovich, Vladik Error estimation for indirect measurements: Interval computation problem is (slightly) harder than a similar probabilistic computational problem. (English) Zbl 0942.65047 Reliab. Comput. 5, No. 1, 81-95 (1999). 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) Cited in 1 Document 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 Keywords:error estimation; computational complexity; interval arithmetic; probabilistic computational problems; indirect measurements; polynomial time algorithm; NP-hardness PDFBibTeX XMLCite \textit{O. Kosheleva} and \textit{V. Kreinovich}, Reliab. Comput. 5, No. 1, 81--95 (1999; Zbl 0942.65047) Full Text: DOI