I wonder what is $K(x|K(x))$, $K$ denoting (Kolmogorov-Chaitin) prefix complexity. Naively, it looks like it should just be $K(x)+O(1)$. Is that right? The same question for plain Kolmogorov complexity is interesting as well.
1
-
$\begingroup$ Not quite the solution, but somewhat close. C(x)=K(x|C(x))+O(1) (Li, Vitányi, Lemma 3.1.1). C(x) is plain Kolmogorov complexity. $\endgroup$– P. TrinliJun 20, 2017 at 15:17
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
For plain complexity the assertion is true. One direction is clear: $K(x|K(x))\leq K(x)$ (easier to describe x from something than from nothing). In the other direction one can argue by contraposition. Suppose one could find $x$s with programs $q$s of length $l(q)$ arbitrarily shorter than $K(x)$. Set $K(x)-l(q) \equiv C$. In other words one can find $x$s with arbitrarily large corresponding $C$s. To reconstruct $x$ one needs to only know $q$ and $C$, which can be encoded in $l(q)+2\log(C)$ bits. Now $K(x)-l(q)-2\log(C) = C-2\log(C)$ which can be made arbitrarily large for sufficiently large $C$. Hence, we have obtained a description of $x$ much shorter than $K(x)$, a contradiction. This may be found as problem 43 in the following book (in Russian): https://www.mccme.ru/free-books/shen/kolmbook.pdf (Vereschagin, Uspensky, Shen, "Kolmogorov complexity and algorithmic randomness").