3
$\begingroup$

Does there exist a universal constant $c$ such that for any strings $x, y$, we have: $$K(xy)\leq K(x) + K(y) + c$$ where $K(\cdot)$ denotes the Kolmogorov Complexity of a binary string and $xy$ means the concatenation of $x$ and $y$? I know the answer to this problem is no but I am seeking a proof for this, any hint?

Update: for reference, this is stated at the top of page 266 in Sipser's famous book "Introduction to the Theory of Computation", third edition, and is listed as Problem 6.19 in the book. I've tried to prove it but didn't succeed, just curious to know what proof technique should be used in order to prove it.

Improve this question
$\endgroup$
2
$\begingroup$

Kolmogorov complexity = length of shortest program to generate a string. Take the program generating x, add the fixed size code that makes it continue with a second program instead of halting, then add the second program generating y.

Improve this answer
$\endgroup$
15
  • $\begingroup$ Yeah I understand such procedure, but note that the problem asks whether it holds for all possible strings $x$ and $y$. So a simple question is: since the length of the program generating $x$/$y$ can vary, fixed size code cannot be used to separate the description of programs generating $x$ and $y$. So this simple procedure will lead to an upper bound like $K(x) + K(y) + 2\min\{\log(K(x)), \log(K(y))\} + c$, not the one being asked. $\endgroup$
    – Han Zhao
    Feb 20 '18 at 13:08
  • 1
    $\begingroup$ @HanZhao Fixed-size code CAN be used to merge the two strings. Why not? In imperative programming, if P outputs $x$ and Q outputs $y$, then P;Q outputs $xy$, and is only a ; longer. Or maybe you need something like x:=P();y:=Q();return (x+y);, which is also $O(1)$ longer. On Turing Machines something similar happens. (Note that the space complexity of the programs is irrelevant here, only its length matters) $\endgroup$
    – chi
    Feb 20 '18 at 14:49
  • $\begingroup$ @chi OK, so let's be a little bit more formal here. Let $< M_x, w_x>$ be the description of the program generating $x$, where $M_x$ is a binary string encoding of the TM and $w_x$ is an input binary string to $M_x$ so that $M_x(w_x) = x$. Make analogy definition to $y$. Now construct a new (universal) TM $M$ that takes the concatenation of $< M_x, w_x>$ and $< M_y, w_y>$ as input and outputs $xy$: $M$ simply simulates $M_x(w_x)$ and then simulates $M_y(w_y)$. $\endgroup$
    – Han Zhao
    Feb 20 '18 at 14:57
  • $\begingroup$ @chi But before $M$ can do so, it needs to precisely extract from its single input string which part corresponds to $x$/$y$. That means $M$ needs to know where $<M_x, w_x>$ ends. One way to do so is to prefix the length of $<M_x, w_x>$ at the beginning of the string so that $M$ knows how to parse exactly, and the length itself can be encoded using the doubling trick with length $2\log(K(x))$, i.e., for length 4 = 100, encode it as 110000, and use a following 01 as a separator. $\endgroup$
    – Han Zhao
    Feb 20 '18 at 15:00
  • 1
    $\begingroup$ @HanZhao You don't need $M$ at all! You only need to prove that given that TMs $M_x,M_y$ exist, then $M_{xy}$ exists and has a suitably bounded length. The transformation from $M_x,M_y$ to $M_{xy}$ is not done by a TM! You are trying to do much more that what it is needed to prove the above inequality. $\endgroup$
    – chi
    Feb 20 '18 at 15:12

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.