We note $K(X)$ the kolmogorov complexity of the word X and $K(X|Y)$ the kolmogorov complexity of $X$ knowing $Y$. Let $M$ an universal turing machine. Let $A$ and $B$ two words, and $P(A)$ a word of minimal size such that the execution of $P(A)$ on $M$ give $A$. We note $(A;B)$ the word $A$ concatenate with $B$. Is it true that $|K((A;B))-K((P(A);B))|< C$, where $C$ is a constant independante of $A$ and $B$ ?

Remark: the result is implied by: $K((A;B)|(P(A);B)) < C_1$ and $K(((P(A);B)|(A;B)) < C_2$ with $C_1$ and $C_2$ constants independant of $A$ and $B$. The first inequality is obvious but the second one require to calculate $P(A)$ from $A$ which is not possible cause Kolmogorov complexity is not calculable.


1 Answer 1


It is not generally true that $K((P(A);B)\vert (A;B))<C_2$ for some constant $C_2$, thus the claim you ask about does not hold.

To see why, consider the simpler case where $B$ is empty, so we consider $K(P(A)|A)$. Assume for the moment that $K(P(A)|A)<C_2$, which implies that the conditional complexity of the Kolmogorov complexity of $A$ would obey $K(K(A)|A)<C_2+C_3$ (where $C_3$ is basically the length of the program that measures and outputs the length of $P(A)$). However, it is known (for both regular and prefix-free) complexity that for every $n$, there exists a string $A$ of length $n$ that obeys $K(K(A)|A) \ge \log n$ up to an additive constant (Theorem 2 in Bauwens and Shen, https://arxiv.org/pdf/1202.6668.pdf), meaning that our assumption leads to a contradiction.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .