What are some examples of problems whose deterministic versions are easy, but become hard when injecting some uncertainty (or randomness of some kind)? What are some examples in which the problems remain feasible? Can one tell in advance?

I am particularly interested in scheduling problems and what to know as to how the uncertainty in information (e.g. processing times of jobs) affects the difficulty of the problems. I believe the problem becomes more difficult when information is uncertain. Is it true?


1 Answer 1


Linear Quadratic Regulation is a standard control-theoretic problem that is easy when deterministic. The problem is to minimize a quadratic cost while steering a linear system:


Interestingly, the problem remains easy when additive Gaussian noise disturbes the system and your observations of it:


However, the problem becomes hard as soon as the noise is non-Gaussian (or even multiplicative Gaussian).

  • $\begingroup$ How about combinatorial optimization problems, scheduling in particular? $\endgroup$
    – kosmos
    Feb 13, 2018 at 3:57
  • 1
    $\begingroup$ I wish I knew anything about that! Looking forward to seeing other examples. $\endgroup$
    – tobwin
    Feb 13, 2018 at 4:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.