MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Thanks to symetry of information (i.e $\forall x,y, K(xy) = K(x) + K(y|x) - O(log(|x| + |y|)$), one can easily show that :

$ \exists N \forall x, (|x| = n^{log(n)} and |x| \geq N), \exists y, (|y| \leq n), K(xy) > K(x) $.

But if we consider the Kolmogorov complexity with bounded ressources (i.e $K^{f(n)}(x)$ is the length of the shortest program that runs in time $f(n)$ and outputs x.

Do we have a similar property, that

$\forall x ,|x| = n^{log(n)}, \exists y, |y| \leq n, K^{2^n}(xy) > K^{2^n}(x) $


share|cite|improve this question
How can you show the first statement? I cannot figure it out. – domotorp Apr 16 '12 at 2:43
We can show $K(xy) \geq K(x) + K(y|x) - O(log(|x| + |y|))$ like that : Let $S = \{ (a,b), K(ab) \leq K(xy) \}$ and $S_a = \{ b, K(ab) \leq K(xy) \}$ We know that $y \in S_x$ so $ K(y|x) \leq log |S_x|$ (we have $|S_x| \geq 2^{K(y|x)} $) Let $A = \{ a, |S_a| \geq 2^{K(y|x)}$ $x \in A \Rightarrow |A| \geq 2^{K(x)}$. Now, we can finish : $S \supseteq \bigcup \{a\}*S_a$ So, $|S| \geq |A|* 2^{K(y|x)}$ but $2^{K(xy)} \geq |S|$ Finally, we have $2^{K(xy)} \geq 2^{K(x) + K(y|x)}$ (not the log term because of some approximation but this is the idea) – user22579 May 2 '12 at 12:53

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.