On Time-Bounded Incompressibility of Compressible Strings and Sequences

E. G. Daylight, W. M. Koolen, P. M. B. Vitanyi

For every total recursive time bound $t$, a constant fraction of all compressible (low Kolmogorov complexity) strings is $t$-bounded incompressible (high time-bounded Kolmogorov co…