Unimodality, independence lead to NP-hardness of interval probability problems

DOI10.1007/S11155-006-9031-4MaRDI QIDQ877251zbMATH OpenOpenAlexFDO

Authors Daniel J. Berleant, Olga Kosheleva, Vladik Kreinovich, Hung T. Nguyen

Publication date 19 April 2007

Published in Reliable Computing (Search for Journal in Brave)

Full work available at URL https://digitalcommons.utep.edu/cgi/viewcontent.cgi?article=1167&context=cs_techrep

zbMATH Keywords

interval probability problemlinear constraintslinear programming problemmomentsNP-hard problem

Mathematics Subject Classification ID

Interval and finite arithmetic (65G30) Numerical mathematical programming methods (65K05)

Review text

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.

Recommendations

• scientific article; zbMATH DE number 3909744
• Simultaneous strong separations of probabilistic and unambiguous complexity classes
• On the unimodality of discrete probability measures
• On random hard sets for NP
• scientific article; zbMATH DE number 1555920
• scientific article; zbMATH DE number 1512688
• Unsatisfiability bounds for random CSPs from an energetic interpolation method
• On the stochastic independence properties of hard-core distributions
• Tight Probability Bounds with Pairwise Independence

Cites work

• A feasible algorithm for locating concave and convex zones of interval data and its use in statistics-based clustering
• Computation of bounds on population parameters when the data are incomplete
• Computational complexity and feasibility of data processing and interval computations
• Computing best-possible bounds for the distribution of a sum of several variables is NP-hard
• Dependable handling of uncertainty
• scientific article; zbMATH DE number 48344 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 804633 (Why is no real title available?)
• Jeffrey's conditioning rule in neighbourhood models
• On the use of capacities in modeling uncertainty aversion and risk aversion
• Partial identification of probability distributions.
• Ranges of posterior measures for priors with unimodal contaminations
• Statool: A tool for distribution envelope determination (DEnv), an interval-based algorithm for arithmetic on random variables
• Using Pearson correlation to improve envelopes around the distributions of functions

Cited in

(2)

• Computing best-possible bounds for the distribution of a sum of several variables is NP-hard
• Interval time series analysis with an application to the sterling-dollar exchange rate

Describes a project that uses

Uses Software

• Statool

This page was built for publication: Unimodality, independence lead to NP-hardness of interval probability problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q877251)