### 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