Denote by $C(n)$ the plain Kolmogorov complexity of $n$ and the length of a binary encoding of $n$ by $l(n)$, why do we have $$ C(n\mid l(n)) \ge C(n) - C(l(n))? $$ If I have a shortest program $p$ for $n$ given $l(n)$ and a shortest program $q$ for $l(n)$, then to compose out of them a program for $n$ (i.e. first compute $l(n)$ and then use this and $p$ to compute $n$) I need some way to tell them apart, thereby I need to put additional information into a program for $n$ using the programs $q$ and $p$, hence I do not have just $C(n) \le C(n\mid l(n)) + C(l(n))$, but this is written in my textbook as holding "clearly"? Or does this just hold if $C(n) \ge l(n)$?

  • $\begingroup$ Are you certain this is plain complexity, rather than prefix-free complexity? $\endgroup$ – Carl Mummert Jul 26 '15 at 20:23
  • $\begingroup$ As a separate point, questions like this are certainly unrelated to descriptive set theory; they are not really related to computational complexity unless we consider some sort of resource-bounded Kolmogorov complexity; and Kolmogorov complexity is not only a "computer science" topic (no more than computability theory in general), so I have edited the tags of the question. $\endgroup$ – Carl Mummert Jul 26 '15 at 20:26
  • $\begingroup$ Yes, I am sure, it is Example 2.2.5 from An Introduction to Kolmogorov Complexity and Its Applications, do you have a copy of this book (if not I can make a screenshot of the relevant page?) and there they just discuss plain Kolmogorov complexity. Thanks for your remarks regarding my tags! $\endgroup$ – StefanH Jul 26 '15 at 20:34

In Example 2.2.5 of Li and Vitanyi, they say that they are looking at a string such that the "pattern of 0s and 1s is very irregular, $C(n) \geq l(n)$". What I believe they mean (added part in italics) is that they are looking at a string such that "the pattern of 0s and 1s is very irregular, that is, $C(n) \geq l(n)$". The final sentence of their example is only intended to apply to that case. The prose in that example is challenging for me to read, overall.

However, as we discussed in the comments, I don't see immediately how to fill in the argument in the book. The overall conclusion seems to be salvageable, as in the comments.

  • $\begingroup$ Thanks for your efforts, but why we have $C(n) \le C(n \mid l(n)) + C(l(n))$, that was my initial question?? (might be obvious but I do not see it...) $\endgroup$ – StefanH Jul 26 '15 at 21:49
  • $\begingroup$ I don't see it either, immediately. There should be an additional term, unless I am missing some special assumption. But the overall conclusion of the argument seems to be sound, which is what I decided I could verify in the answer. $\endgroup$ – Carl Mummert Jul 26 '15 at 22:08
  • $\begingroup$ Ok. As I see it the inequality $C(n) \le C(n\mid l(n)) + C(l(n))$ is essential, but could we derive the conclusion if we have an additonal term $C(n) \le C(n|l(n) + C(l(n)) + f(n)$? In that case using $\log n \le C(n)$ we have $C(n|l(n)) \ge \log(n) - 2\log\log n - r - f(n)$. We could achieve $f(n) = 2\log\log n+1$ by coding the length of $l(n)$ (self-delimiting) into the input, then we have $$ C(n | l(n)) \ge \log(n) - 4\log\log n - r - 1 $$ and the same conclusion could be drawn. Might it be possible that this is an error in the book and the authors just forgot about the additional term? $\endgroup$ – StefanH Jul 26 '15 at 22:21
  • $\begingroup$ You say: "Start with $C(n) \le C(n|l(n)) + C(l(n))$, which is true anyway"??? I am confused by what you are saying... why now you accept that it is true and a few comment above you share my objections that this might not be true (or is not obvious)??? As I see it your reasoning just works if someone accepts this inequality as true, but exactly that inequality is under discussion... $\endgroup$ – StefanH Jul 26 '15 at 23:38
  • $\begingroup$ You're right - I'm going to delete that part of the answer. We agree that it should say that $C(n) \leq C(n|l(n)) + C(l(n)) + f(n)$ for an appropriate and unbounded $f(n)$. Apparently I was trying too hard to salvage the argument in the text, and began to work as if their inequality was actually right. But your version of the argument also gives the right conclusion. $\endgroup$ – Carl Mummert Jul 26 '15 at 23:42

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.