On time-bounded incompressibility of compressible strings
Edgar Graham Daylight, Wouter M. Koolen, Paul M. B. Vitanyi · UvA-DARE (University of Amsterdam) · 2008
We prove that there exist finite strings with very low Kolmogorov complexity that have very high time-bounded Kolmogorov complexity. Such strings are compressible but time-bounded incompressible. For every total recursive time bound t, a constant fraction of all compressible strings is t-bounded incompressible.