Engineering Design under Imprecise Probabilities: Computational Complexity

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 requiremen...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autor principal:	Kreinovich,Vladik
Lenguaje:	English
Publicado:	Universidad de La Frontera. Departamento de Matemática y Estadística. 2011
Materias:	Engineering design imprecise probability computational complexity p-boxes NP-hard
Acceso en línea:	http://www.scielo.cl/scielo.php?script=sci_arttext&pid=S0719-06462011000100007
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:scielo:S0719-06462011000100007
record_format	dspace
spelling	oai:scielo:S0719-064620110001000072018-10-08Engineering Design under Imprecise Probabilities: Computational ComplexityKreinovich,Vladik Engineering design imprecise probability computational complexity p-boxes NP-hard 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.info:eu-repo/semantics/openAccessUniversidad de La Frontera. Departamento de Matemática y Estadística.Cubo (Temuco) v.13 n.1 20112011-01-01text/htmlhttp://www.scielo.cl/scielo.php?script=sci_arttext&pid=S0719-06462011000100007en10.4067/S0719-06462011000100007
institution	Scielo Chile
collection	Scielo Chile
language	English
topic	Engineering design imprecise probability computational complexity p-boxes NP-hard
spellingShingle	Engineering design imprecise probability computational complexity p-boxes NP-hard Kreinovich,Vladik Engineering Design under Imprecise Probabilities: Computational Complexity
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 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.
author	Kreinovich,Vladik
author_facet	Kreinovich,Vladik
author_sort	Kreinovich,Vladik
title	Engineering Design under Imprecise Probabilities: Computational Complexity
title_short	Engineering Design under Imprecise Probabilities: Computational Complexity
title_full	Engineering Design under Imprecise Probabilities: Computational Complexity
title_fullStr	Engineering Design under Imprecise Probabilities: Computational Complexity
title_full_unstemmed	Engineering Design under Imprecise Probabilities: Computational Complexity
title_sort	engineering design under imprecise probabilities: computational complexity
publisher	Universidad de La Frontera. Departamento de Matemática y Estadística.
publishDate	2011
url	http://www.scielo.cl/scielo.php?script=sci_arttext&pid=S0719-06462011000100007
work_keys_str_mv	AT kreinovichvladik engineeringdesignunderimpreciseprobabilitiescomputationalcomplexity
_version_	1714206771451527168

Engineering Design under Imprecise Probabilities: Computational Complexity

Ejemplares similares