If $t$ is a time constructible function then we can define the time-bounded Kolmogorov complexity of a string $x$ as:

$C^t(x)$ = the size of the smallest program p that generates $x$ in $t(|x|)$ steps

We can also extend the incompressibility notion: a string $x$ is incompressible if $C^t(x) \ge |x|$ (otherwise $x$ is compressible).

Now we can define the function:

$f^t(n) = | \{ x \text{ : } |x|=n \text{ and } x \text{ is compressible with respect to } C^t \} |$

( $f^t(n)$ is the total number of compressible strings of length n ).

What is the relation (if any) between $t$ and the rate of growth of $f$? Can we say something about it?

EDIT: For example, can we choose $t$ to make $f$ grow polynomially? ... NO


1 Answer 1


I suspect that there is something that can be said generally, but off the cuff, the best I can see is that as $t$ increases, the number of compressible strings increases as well.

On the other hand, we certainly cannot pick a $t$ such that $f$ is polynomial. Notice that if $t(|x|)<|x|$, then there isn't enough time to write anything. On the other hand, strings of the form $yyz$ can be generated by programs of length $|y|+|z|<|x|$ and there are at least $2^{|x|/2}$ of those. So by monotonicity, $f$ will always be at least this large.

  • $\begingroup$ thanks. I edited the question. Actually, to make $f$ grow polynomially we must change its definition to $f^t(n) = | \{ x : |x|\leq n \text{ and } C^t(x) \leq k \log{x} \} |$ and choose $t(x) = |x|^k$ (P-printable) $\endgroup$ Commented May 10, 2011 at 8:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.