{"id":"arxiv/2605.03556","url":"https://arxiv.org/abs/2605.03556","tags":["cs.CC","math.CO","math.PR"],"score":0,"title":"Optimal Union Probability Interval Is NP-Hard","domain":"cs.CC","source":"arxiv","authors":["Petteri Kaski","Heikki Mannila","Chandra Kanta Mohapatra"],"reviews":0,"subject":"cs.CC","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-05-05","reactions":{}}