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?