ON THE RELATION BETWEEN COMPLEXITY AND UNCERTAINTY.

In practical problem situations data are usually inherently unreliable. A mathematical representation of uncertainty leads to stochastic optimization problems. In this paper the complexity of stochastic combinatorial optimization problems is discussed. Surprisingly, certain stochastic versions of NP-hard deterministic combinatorial problems appear to be solvable in polynomial time. [ABSTRACT FROM AUTHOR]