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.