In his book "Theoretical Computer Science", Juraj Hromkovic informally defines the Kolmogorov complexity $K(x)$ of a word $x$ consisting of zeros and ones as the binary length of the shortest Pascal program that generates $x$. The Kolmogorov complexity $K(n)$ of a natural number $n$ is then defined as the Kolmogorov complexity of the binary representation of $n$.

To show that there's a constant $d$ such that $K(x)\leq|x|+d$ for all words $x$ (where $|x|$ is the length of $x$), he uses the following (pseudo) program $A_x$ to generate $x$:


But he notes (in the 2007 German edition of the book, but not in the 2004 English edition) that we would have to prefix the code with two numbers $k$ and $l$ with $k$ being the length of the (constant) "prefix" of the program (up to and including the opening parenthesis) and $l$ being the length of the "suffix" (starting with the closing parenthesis). The reason for this is that we can thus store $x$ verbatim (as a sequence of ones and zeros) while the constant part of the program is the same for each $x$ (and responsible for the constant $d$ above).

So far, so good. I can understand how this is supposed to work, but because he tries to avoid encoding the length of $x$ into the program (as he writes himself) we obviously have to know where the program ends to make sense of $l$. (One could for example image that one receives $A_x$ as a file.)

But two pages later there's an exercise where he claims that for a positive natural number $n=pq$ we have $K(n)\leq K(p)+K(q)+c$ with a constant $c$ independent of $n$, $p$, and $q$. I think the basic idea here is that $c$ is the length of a program that executes the corresponding programs for the two factors and multiplies them. But if the programs for $p$ and $q$ are programs like above we would need to know how long they are - which we don't. I can easily see how to prove $K(n)\leq 2\max(K(p),K(q))+c$ or $K(n)\leq K(p)+\log_2(K(p))+K(q)+c$ or something similar, but I'm at loss regarding $K(n)\leq K(p)+K(q)+c$. Any ideas?

  • 1
    $\begingroup$ Seems like a mistake. This kind of inequality holds for self-delimiting Kolmogorov complexity (often denoted $C(\cdot)$), which doesn't satisfy $K(x) \leq |x| + O(1)$. $\endgroup$ May 17 '20 at 14:56

Your Answer

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

Browse other questions tagged or ask your own question.