Comment Re:if I understand your point (Score 2) 169
no, you got it only the half way.
deterministic:
best = np-hard, perfekt
other: polynomial, good average
stochastic:
best: np-hard, not perfect, quality unknown
other: polynomial, good average
the point is not the runtime complexity, but the result. while the best algorithm cannot be beaten on the det. sequence, it may fail completely (in terms of quality) on a sequence without full information. If you got a good polynomial one with an average result, it may be better for many sequences.
one example may be an perfect algorithm with a lookup table for all sequences and a greedy algorithm.
With the random sequence, the "perfect" algorithm needs to choose the sequence which is most likely for its next move, discarding a lot of other strategies. Now it may have chosen the worst strategy for the next random and unlikely event. The other algorithm optimizes locally anyway and will continue in both cases as if it does not know the next event.