7
$\begingroup$

I know that the Kolmogorov complexity of a substring $v$ of an incompressible string $x$ has $C(v)\geq |v|-O(\log{|x|})$ , but I'm wondering if it is also possible to infer the complexity of a string given its substrings' complexity:

Specifically, If $x$ is a string of length $n$ and every substring $v$ of $x$ having length $m$ has complexity $C(v)\geq k$, is it possible to infer any general lower bound for $C(x)$ in terms of $n$, $m$, and $k$? I'm thinking that $C(x)$ cannot be much smaller than $k$ or else the $C(v)$ would not have $k$ as a lower bound. On the other hand, since $n$ can be much larger than $m$ this might balance things out.

$\endgroup$
1
$\begingroup$

A simple bound is that we could use a program generating $x$, a starting index $1 \leq i \leq n$ and length $m$ to get a program generating any choice of $v$, and thus $C(v)$ is bounded as

$$\forall v: k \leq C(v) \leq C(x) + \log(n) + \log(m) + c,$$

where $c$ is some constant overhead independent from $x,v$ that represents the steps necessary to take a Turing machine, a starting index and length and return the requested substring.

This in turn gives us a lower bound for $C(x)$,

$$C(x) \geq k - \log(n) - \log(m) - c.$$

$\endgroup$
4
  • $\begingroup$ Thanks. I thought though that a string always has a kolmogorov complexity at least as high as any of its substrings'. (In this case $C(x)\geq k$ without a need to subtract any more). Is that not necessarily true? $\endgroup$
    – Ari
    Dec 28 '20 at 14:04
  • $\begingroup$ @Ari No. Consider a program that generates all strings up to length $n$ concatenated. $\endgroup$
    – orlp
    Dec 28 '20 at 19:51
  • $\begingroup$ Thanks for the clarification. I also thought about it more and realized that without knowing any more about $x$, yours is about the best bound we can hope for. That is, if $x$ is $\frac{n}{m}$ copies of $v$ concatenated, we get $C(x)\leq k+O(\log(\frac{n}{m}))$. $\endgroup$
    – Ari
    Dec 29 '20 at 23:26
  • $\begingroup$ @Ari I didn't claim my bound was the best possible, and your original question was more generic than copies of $v$ concatenated (the substrings could overlap in your original question). So I wouldn't be so quick with your conclusion. $\endgroup$
    – orlp
    Dec 29 '20 at 23:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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