On the complexity of two-stage stochastic linear optimization with small second stage

Abstract

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 #P-hardness in case the number of second-stage constraints is fixed, while fixing the number of second-stage variables leads to a weakly #P-hard problem. Finally, if both the dimension of the random vector and the number of second-stage constraints are fixed, the problem turns out to be tractable.

Explicit second-order min-max optimization: Practical algorithms and complexity analysis
Tianyi Lin, Panayotis Mertikopoulos, Michael I. Jordan
Transactions on Machine Learning Research26 May 2026Peer-reviewedCC BY 4.0Full textOptimisation & controlHAL
Stochastic Augmented Lagrangian Framework with Second-Order Convergence Guarantees for Nonconvex Expectation-Constrained Optimization
Raghu Bollapragada, Yash Kumar
arXiv23 Sep 2026PreprintarXiv licenceFull textOptimisation & controlarXiv
On the Complexity of Finding Stationary Points in Stochastic (L₀, L₁)-Smooth Nonconvex Optimization
Yanpeng Liang, Luo Luo
arXiv15 Oct 2026PreprintCC BY 4.0Full textOptimisation & controlarXiv
Application of Optimal Inexact Second-Order Acceleration to Distributed Stochastic Optimization under Statistical Similarity
Yury A. Sokolov, Maxim K. Mashtaler, Alexander V. Gasnikov +3
arXiv18 Sep 2026PreprintCC BY 4.0Full textOptimisation & controlarXiv
Matching Complexity for Second-Order Stationary Point with Sample Reuse
Qian Chen, Wendao Wu, Haihan Zhang +5
arXiv19 Oct 2026PreprintarXiv licenceFull textOptimisation & controlarXiv

Cite

BibTeX RIS

BibTeX

@misc{buchheim2026complexity,
  title = {{On the complexity of two-stage stochastic linear optimization with small second stage}},
  author = {Christoph Buchheim},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2605.25028},
  eprint = {2605.25028},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2605.25028},
  note = {CC BY 4.0},
}

RIS

TY  - UNPB
TI  - On the complexity of two-stage stochastic linear optimization with small second stage
AU  - Christoph Buchheim
PY  - 2026
DA  - 2026/10/17
PB  - arXiv
DO  - 10.48550/arxiv.2605.25028
UR  - https://arxiv.org/abs/2605.25028
AB  - 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 #P-hardness in case the number of second-stage constraints is fixed, while fixing the number of second-stage variables leads to a weakly #P-hard problem. Finally, if both the dimension of the random vector and the number of second-stage constraints are fixed, the problem turns out to be tractable.
ER  -

Abstract

Related

Cite