Fix your favorite programming language and let K(x) be the length of
the smallest program generating string x. Define
μ(x)=2^{-K(x)}, known as the universal distribution for
reasons I won't get into here. Notice how strings of smaller
complexity get more weight.

**Theorem (Li-Vitányi)** Any algorithm using time T(n) on
average over the universal distribution uses time O(T(n)) in the worst
case.

Li and Vitányi prove their theorem by showing that if the set of worst-case inputs is small they will have a short description and thus more heavily weighted under μ. Read all the details in their paper.

## No comments:

## Post a Comment