What are some examples of problems whose deterministic versions are easy, but become hard when injecting some uncertainty?

Question

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?

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:

https://en.wikipedia.org/wiki/Linear%E2%80%93quadratic_regulator

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

https://en.wikipedia.org/wiki/Linear%E2%80%93quadratic%E2%80%93Gaussian_control

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