1
$\begingroup$

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.

$\endgroup$
  • $\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. Trinli Jun 20 '17 at 15:17
2
$\begingroup$

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").

$\endgroup$

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.