A Tight Upper Bound on Kolmogorov Complexity by Hausdorff Dimension and
Uniformly Optimal Prediction

Ludwig Staiger

           The present paper links the concepts of Kolmogorov complexity
           (in Complexity theory) and Hausdorff dimension (in Fractal
           geometry) for a class of recursive (computable) sets of
           infinite strings.

           It is shown that the complexity of an infinite string contained
           in a \Sigma_2-definable set of strings is upper bounded
           by the Hausdorff dimension of this set and that this upper
           bound is tight. Moreover, we show that there are computable
           gambling strategies guaranteeing a uniform prediction quality
           arbitrarily close to the optimal one estimated by Hausdorff
           dimension and Kolmogorov complexity provided the gambler's
           adversary plays according to a sequence chosen from a
           \Sigma_2-definable set of strings.

           We provide also examples which give evidence that our results
           do not extend further in the Arithmetical hierarchy.