Unimodality, Independence Lead to NP-Hardness of Interval Probability Problems

Author： Berleant Daniel  

Publisher： Springer Publishing Company

ISSN： 1385-3139

Source： Reliable Computing, Vol.13, Iss.3, 2007-06, pp. : 261-282

Disclaimer: Any content in publications that violate the sovereignty, the constitution or regulations of the PRC is not accepted or approved by CNPIEC.

Previous Menu Next

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.

Related content

Strong NP-hardness of scheduling problems with learning or aging effect

By Janiak Adam  

Annals of Operations Research, Vol. 206, Iss. 1, 2013-07 ,pp. : 577-583 (7)

Springer Publishing Company

Access to resources Recommend Favorite

NP-hardness of Euclidean sum-of-squares clustering

By Aloise Daniel  

Machine Learning, Vol. 75, Iss. 2, 2009-05 ,pp. : 245-248 (4)

Springer Publishing Company

Access to resources Recommend Favorite

Approximation of some NP-hard optimization problems by finite machines, in probability

By Hong D.   Birget  

Theoretical Computer Science, Vol. 259, Iss. 1, 2001-05 ,pp. : 323-339 (17)

Elsevier

Access to resources Recommend Favorite

NP-Hardness of Broadcast Scheduling and Inapproximability of Single-Source Unsplittable Min-Cost Flow: Special Issue on Scheduling

By Erlebach Thomas   Hall Alexander  

Journal of Scheduling, Vol. 7, Iss. 3, 2004-05 ,pp. : 223-241 (19)

Springer Publishing Company

Access to resources Recommend Favorite

Complete problems for monotone NP

By Stewart I.A.  

Theoretical Computer Science, Vol. 145, Iss. 1, 1995-07 ,pp. : 147-157 (11)

Elsevier

Access to resources Recommend Favorite