<p>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.</p>

<p>On the other hand, we certainly cannot pick a $t$ such that $f$ is polynomial.  Notice that if $t(|x|)&lt;|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|&lt;|x|$ and there are at least $2^{|x|/2}$ of those.  So by monotonicity, $f$ will always be at least this large.</p>

CC BY-SA 3.0
2011-05-10T08:20:44.630Z
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*)
Marzio De Biasi
CC BY-SA 3.0
2011-05-09T22:53:02.397Z
2011-05-09T22:53:02.397Z
Aubrey da Cunha
<p>If $t$ is a time constructible function then we can define the <strong>time-bounded Kolmogorov complexity</strong> of a string $x$ as:</p>

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

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

<p>Now we can define the function:</p>

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

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

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

<p><strong>EDIT:</strong>
For example, can we choose $t$ to make $f$ grow polynomially? ... <strong>NO</strong></p>

<cc.complexity-theory><kolmogorov-complexity>
Time-bounded Kolmogorov complexity and non-random strings
Marzio De Biasi
# Time-bounded Kolmogorov complexity and non-random strings

(Asked by: username_0 on 2011-05-09)

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**

**Tags:** cc.complexity-theory, kolmogorov-complexity


---

## 1 answers

### Answer by username_1 on 2011-05-09. Score: 3 | Accepted answer

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.

> **Comments:**
> **username_0**: 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*)  

---

