Universal Distributions and Time-Bounded Kolmogorov Complexity

Author: Rainer Schuler

Source: Proc. 16th Annual Symposium on Theoretical Aspects of Computer Science - STACS'99, March 4-6, Trier, Germany, Lecture Notes in Computer Science 1563, pp. 434 - 443, Springer-Verlag 1999.

Abstract. The equivalence of the universal distribution, the a priori probability and the negative exponential of Kolmogorov complexity is a well known result. The natural analogs of Kolmogorov complexity and of a priori probability in the time-bounded setting are not efficiently computable under reasonable assumptions. In contrast, it is known that for every polynomial p, distributions universal for the class of p-time computable distributions can be computed in polynomial time. We show that in the time-bounded setting the universal distribution gives rise to sensible notions of Kolmogorov complexity and of a priori probability.

©Copyright 1999, Springer-Verlag