Abstract für Paper
Autor: Rainer Schuler
To appear in the Proceedings of the 16th Annual Symposium on Theoretical Aspects of Computer Science, 1999.
Abstract:
Universal distributions play a central role in the average-case
analysis of algorithms. In the unbounded (r.e.) setting the
worst-case complexity of an algorithm even coincides with the
average-case complexity with respect to the universal distribution.
Furthermore, in the simple PAC-learning model of Li and Vitanyi, a
concept class is learnable (with respect to any simple distribution)
if it is learnable with respect to the universal distribution.
Similar results hold in the time bounded setting. Recently, it has
been shown that for every polynomial p, distributions universal
for the class of p-time computable distributions can be computed
in polynomial-time. We show that unlike the unbounded case, the time
bounded universal distributions give rise to a possibly different
notion of time bounded prefix Kolmogorov complexity.
Kontaktadresse:
schuler@informatik.uni-ulm.de