2026-08-25T18:47:25Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27265 2026-08-25T13:18:20Z ddc:004 open_access

Optimal Union Probability Interval Is NP-Hard Kaski, Petteri Mannila, Heikki Mohapatra, Chandra Kanta combinatorial probability computational complexity correlation polytope generalized Bonferroni inequalities graphical models inclusion-exclusion intersection probability linear programming union polytope A problem dating back to Boole [Laws of Thought, Walton & Maberly, 1854] is what can be computed about the probability of a finite union of events when given as input the probabilities of intersections of some of the events. The modern geometric study of the problem can be traced back to Hailperin [Amer. Math. Monthly 2 (1965) 343-359] who phrased the problem in the language of linear programming and generalized it to logical formulas of the events other than disjunction, heralding a substantial body of work in probabilistic logic [Nilsson, Artif. Intell. 28 (1986) 71-87], including the probabilistic satisfiability problem of Georgakopoulos, Kavvadis, and Papadimitriou [J. Complexity 4 (1988) 1-11], as well as fundamental connections to the geometry of metrics via cut and correlation polytopes [Deza and Laurent, Geometry of Cuts and Metrics, Springer, 1997] and to the study of marginal polytopes in graphical models of machine learning [Wainwright and Jordan, Found. Trends Mach. Learn. 1 (2008) 1-305]. This paper (i) describes the pertinent geometry of Boole’s problem via coordinate projections of an elementary polytope arising essentially from Hailperin’s linear program on the atoms of a Venn diagram, and (ii) shows that computing the optimal interval for the union probability is NP-hard, resolving an apparent gap in the literature highlighted by Pitowsky [Math. Programming 50 (1991) 395-414] and Boros et al. [Math. Oper. Res. 39 (2014) 1311-1329 and 51 (2026) 134-148]. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Petteri Kaski and Heikki Mannila and Chandra Kanta Mohapatra 2026 Is Part Of LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2026.129 urn:nbn:de:0030-drops-272650 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.129 eng https://creativecommons.org/licenses/by/4.0/legalcode