# Is this kolmogorov complexity inequality true?

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.

It is not generally true that $$K((P(A);B)\vert (A;B)) 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), which implies that the conditional complexity of the Kolmogorov complexity of $$A$$ would obey $$K(K(A)|A) (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.