Time-Bounded Universal Distributions
Lance Fortnow, Luís Filipe Antunes · Electronic colloquium on computational complexity · 2005
We show that under a reasonable hardness assumptions, the time-bounded Kolmogorov distribution is a universal samplable distribution. Under the same assumption we exactly characterize the worst-case running time of languages that are in average polynomial-time over all P-samplable distributions.