%0 Journal Article
%T Engineering Design under Imprecise Probabilities: Computational Complexity
%A Kreinovich
%A Vladik
%J Cubo (Temuco)
%D 2011
%I Scientific Electronic Library Online
%R 10.4067/S0719-06462011000100007
%X in engineering design problems, we want to make sure that a certain quantity c of the designed system lies within given bounds - or at least that the probability of this quantity to be outside these bounds does not exceed a given threshold. we may have several such requirements - thus the requirement can be formulated as bounds [fc(x), fc(x)] on the cumulative distribution function fc(x) of the quantity c; such bounds are known as a p-box. the value of the desired quantity c depends on the design parameters a and the parameters b characterizing the environment: c = f(a, b). to achieve the design goal, we need to find the design parameters a for which the distribution fc(x) for c = f(a, b) is within the given bounds for all possible values of the environmental variables b. the problem of computing such a is called backcalculation. for b, we also have ranges with different probabilities - i.e., also a p-box. thus, we have backcalculation problem for p-boxes. for p-boxes, there exist efficient algorithms for finding a design a that satisfies the given constraints. the next natural question is to find a design that satisfies additional general, the problem of finding such a design is computationally difficult (np-hard). we show that this problem is np-hard already in the simplest possible linearized case, when the dependence c = f(a, b) is linear. we also provide an example when an efficient algorithm is possible.
%K engineering design
%K imprecise probability
%K computational complexity
%K p-boxes
%K np-hard.
%U http://www.scielo.cl/scielo.php?script=sci_abstract&pid=S0719-06462011000100007&lng=en&nrm=iso&tlng=en