Time-bounded Kolmogorov complexity and non-random strings

Question

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

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.