{"id":"arxiv/2605.25028","url":"https://arxiv.org/abs/2605.25028","tags":["math.OC"],"score":0,"title":"On the complexity of two-stage stochastic linear optimization with small second stage","domain":"math.OC","source":"arxiv","authors":["Christoph Buchheim"],"reviews":0,"subject":"math.OC","summary":"Two-stage stochastic linear optimization is known to be #P-hard when all involved random variables are independently and uniformly distributed over intervals, even with fixed recourse. We show that this problem is in fact #P-hard in the strong sense. More surprisingly, #P-hardness persists even when the random vector is one-dimensional, i.e., uniformly distributed over a single interval. To obtain this result, we show that computing the area of a two-dimensional polytope given by a compact extended formulation is #P-hard. Furthermore, for a problem in standard form, we prove strong…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-05-24","reactions":{}}