Unimodality, independence lead to NP-hardness of interval probability problems (Q877251): Difference between revisions

The authors consider probability distributions on the two-dimensional grid \(N^2\). The interval probability problem (IPP) is to check whether there exist a distribution which satisfy a given finite list of linear constraints (say, inequalities on functional moments). A set of additional constraints is considered, such as unimodality of the 2D distributions, unimodality of 1D conditional distributions, independence of entries, convexity of level sets. It is shown that adding any of these conditions to IPP turns it to a NP-hard problem.