Engineering Design under Imprecise Probabilities: Computational Complexity
Владик Крейнович · Cubo · 2011
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 [F c (x), F c (x)] on the cumulative distribution function F c (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 F c (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 104 Vladik Kreinovich CUBO 13, 1 (2011) constraints: on the cost, on the efficiency, etc.In this paper, we prove that that in 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. RESUMENEn los problemas de diseño de ingeniería, en los que quiere asegurarse de que una determinada cantidad c del sistema se encuentra dentro de los límites dados -o por lo menos que la probabilidad de esa cantidad fuera de estos límites no superen un determinado umbral.Es posible que haya varios requisitos -la exigencia puede formularse como límites [F c (x), F c (x)] en la función de distribución acumulada F c (x) de la cantidad de c, esos límites son conocidos como p-caja.El valor de la cantidad deseada c depende de los parámetros de diseño a y los parámetros b caracterizar el medio ambiente: c = f (a, b).Para lograr el objetivo de diseño, tenemos que encontrar los parámetros de diseño a para que la distribución de F c (x) para c = f (a, b) esté dentro de los límites dados por todos los valores posibles de las variables ambientales b.El problema de la informática se llama a retrocálculo.Por b, también tienen rangos con diferentes probabilidades, es decir, también una p-box.Por lo tanto, tenemos un problema de retrocálculo para p-cajas.Para p-cajas, existen algoritmos eficientes para encontrar un diseño a que satisface las restricciones dadas.La pregunta lógica es encontrar un diseño que satisfaga restricciones adicionales: el coste, la eficiencia, etc. En este trabajo, demostramos, en general, el problema de encontrar un diseño que es computacionalmente difícil (NPhard).Se demuestra que este problema es NP-hard ya en el caso lineal más simple posible, cuando la dependencia c = f (a, b) es lineal.También ofrecemos un ejemplo, cuando un algoritmo eficiente es posible.