A comment on “computational complexity of stochastic programming problems”

Grani A. Hanasusanto, Daniel Kuhn, Wolfram Wiesemann

Research output: Contribution to journalArticlepeer-review


Although stochastic programming problems were always believed to be computationally challenging, this perception has only recently received a theoretical justification by the seminal work of Dyer and Stougie (Math Program A 106(3):423–432, 2006). Amongst others, that paper argues that linear two-stage stochastic programs with fixed recourse are #P-hard even if the random problem data is governed by independent uniform distributions. We show that Dyer and Stougie’s proof is not correct, and we offer a correction which establishes the stronger result that even the approximate solution of such problems is #P-hard for a sufficiently high accuracy. We also provide new results which indicate that linear two-stage stochastic programs with random recourse seem even more challenging to solve.

Original languageEnglish (US)
Pages (from-to)557-569
Number of pages13
JournalMathematical Programming
Issue number1-2
StatePublished - Sep 1 2016
Externally publishedYes


  • Complexity theory
  • Stochastic programming
  • Two-stage problems

ASJC Scopus subject areas

  • Software
  • General Mathematics


Dive into the research topics of 'A comment on “computational complexity of stochastic programming problems”'. Together they form a unique fingerprint.

Cite this