Unimodality,Independence Lead to NP-Hardness of Interval Probability Problems |
| |
| Authors: | Daniel J Berleant Olga Kosheleva Vladik Kreinovich Hung T Nguyen |
| |
| Affiliation: | (1) Department of Information Science, University of Arkansas at Little Rock, ETAS Building, Room 259c, 2801 South University Avenue, Little Rock, Arkansas 72204, USA;(2) NASA Pan-American Center for Earth and Environmental Studies (PACES), University of Texas, El Paso, TX 79968, USA;(3) Department of Mathematical Sciences, New Mexico State University, Las Cruces, NM 88003, USA |
| |
| Abstract: | In many real-life situations, we only have partial information about probabilities. This information is usually described
by bounds on moments, on probabilities of certain events, etc. –i.e., by characteristics c(p) which are linear in terms of the unknown probabilities p
j. If we know interval bounds on some such characteristics  , and we are interested in a characteristic c(p), then we can find the bounds on c(p) by solving a linear programming problem.
In some situations, we also have additional conditions on the probability distribution –e.g., we may know that the two variables
x
1 and x
2 are independent, or that the joint distribution of x
1 and x
2 is unimodal. We show that adding each of these conditions makes the corresponding interval probability problem NP-hard. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
