{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreib3gcac62veqvy6n4tqjhsdfel5bcpfawmyt4vwlztsw2bpb7ghk4",
    "uri": "at://did:plc:3fychdutjjusoqeq24ljch6q/app.bsky.feed.post/3ml62usuyqgg2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2605.03556v1",
  "publishedAt": "2026-05-06T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Petteri Kaski",
    "Heikki Mannila",
    "Chandra Kanta Mohapatra"
  ],
  "textContent": "**Authors:** Petteri Kaski, Heikki Mannila, Chandra Kanta Mohapatra\n\nA 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].",
  "title": "Optimal Union Probability Interval Is NP-Hard"
}