O. Kosheleva, V. Kreinovich Error Estimation for Indirect Measurements : Interval Computation Problem is (Slightly) Harder than a Similar Probabilistic Computational Problem Une des principales applications du calcul d'intervalles est l'estimation d'erreurs de mesurages indirects. Une quantité y est mesurée indirectement si l'on mesure des quantités x1,...,xn liées à y, puis que l'on estime y à partir des résultats X1,...,Xn de ces mesurages par l'intermédiaire de f(X1,...,Xn) en utilisant une fonction connue f. Les calculs d'intervalles sont utilisés pour trouver les valeurs de f(x1,...,xn) quand on sait que les xi appartiennent à des intervalles [Xi-Di,Xi+Di], où les Di sont des précisions garanties des mesurages directs. On sait que le problème correspondant est NP-difficile, même pour des fonctions polynomiales f. Dans certaines situations réelles, on connaît les probabilités des différentes valeurs de xi; en général les erreurs xi-Xi sont des variables aléatoires gaussi­ ennes indépendantes, de moyenne nulle et de déviation standard connue si. Pour de telles situations, on peut formuler un problème probabiliste similaire : étant donné si, on calcule la déviation standard de f(x1,...,xn). Il est raisonnablement facile de montrer que ce problème est faisable pour des fonctions poly­ nomiales f. Donc, pour un polynôme f, le problème du calcul prob­ abiliste est plus facile que le problème du calcul d'intervalles. Il n'est pas beaucoup plus facile. En fait, les polynômes peu­ vent être décrits comme des fonctions obtenues à partir de xi en appliquant l'addition, la soustraction et la multiplication. Une extension naturelle est d'ajouter la division pour obtenir des fonctions rationnelles. Nous prouvons que, pour des fonctions ra­ tionnelles, le problème du calcul probabiliste (issu de l'estimation d'erreur pour des mesurages indirects) est NP- difficile. One of main applications of interval computations is estimating errors of indirect measurements. A quantity y is measured indi­ rectly if we measure some quantities x1,...,xn related to y and then estimate y from the results X1,...,Xn of these measurements as f(X1,...,Xn) by using a known relation f. Interval computa­ tions are used to find the range of f(x1,...,xn) when xi are known to belong to intervals [Xi-Di,Xi+Di], where Di are guaran­ teed accuracies of direct measurements. It is known that the cor­ responding problem is intractable (NP-hard) even for polynomial functions f. In some real-life situations, we know the probabilities of dif­ ferent value of xi; usually, the errors xi-Xi are independent Gaussian random variables with 0 average and known standard devi­ ations si. For such situations, we can formulate a similar proba­ bilistic problem: given si, compute the standard deviation of f(x1,...,xn). It is reasonably easy to show that this problem is feasible for polynomial functions f. So, for polynomial f, the probabilistic computation problem is easier than the interval computation problem. It is not too much easier: Indeed, polynomials can be described as functions obtained from xi by applying addition, subtraction, and multiplication. A natural expansion is to add division, thus getting rational functions. We prove that for rational functions, probabilistic computational problem (emerging from error estima­ tion for indirect measurements) is NP-hard.