| dc.creator | Kreinovich, Vladik | |
| dc.date | 2011-03-01 | |
| dc.identifier | https://revistas.ufro.cl/ojs/index.php/cubo/article/view/1384 | |
| dc.identifier | 10.4067/S0719-06462011000100007 | |
| dc.description | 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 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. | en-US |
| dc.format | application/pdf | |
| dc.language | eng | |
| dc.publisher | Universidad de La Frontera. Temuco, Chile. | en-US |
| dc.relation | https://revistas.ufro.cl/ojs/index.php/cubo/article/view/1384/1236 | |
| dc.source | CUBO, A Mathematical Journal; Vol. 13 No. 1 (2011): CUBO, A Mathematical Journal; 103–123 | en-US |
| dc.source | CUBO, A Mathematical Journal; Vol. 13 Núm. 1 (2011): CUBO, A Mathematical Journal; 103–123 | es-ES |
| dc.source | 0719-0646 | |
| dc.source | 0716-7776 | |
| dc.subject | Engineering design | en-US |
| dc.subject | imprecise probability | en-US |
| dc.subject | computational complexity | en-US |
| dc.subject | p-boxes | en-US |
| dc.subject | NP-hard | en-US |
| dc.title | Engineering design under imprecise probabilities: computational complexity | en-US |
| dc.type | info:eu-repo/semantics/article | |
| dc.type | info:eu-repo/semantics/publishedVersion | |
