  We study problems with stochastic uncertainty information on intervals for
which the precise value can be queried by paying a cost. The goal is to devise
an adaptive decision tree to find a correct solution to the problem in
consideration while minimizing the expected total query cost. We show that, for
the sorting problem, such a decision tree can be found in polynomial time. For
the problem of finding the data item with minimum value, we have some evidence
for hardness. This contradicts intuition, since the minimum problem is easier
both in the online setting with adversarial inputs and in the offline
verification setting. However, the stochastic assumption can be leveraged to
beat both deterministic and randomized approximation lower bounds for the
online setting.
