In what follows $K(x|y)$ is conditional Kolmogorov complexity, $xx$ is $x$ concatenated with itself. It appears to me that $K(xx|yy)=K(xx)$ should be true for infinitely many strings $x$ and $y$. In fact, it seems this should be true "generically" (in some appropriate sense). How hard is this to show (if true)?

  • $\begingroup$ What description language does your K use? ​ ​ $\endgroup$
    – user12859
    May 6 '17 at 22:56
  • $\begingroup$ I believe you mean one must fix some specific universal machine in the definition of K? I assumed this choice will be irrelevant for the answer, won't it? $\endgroup$
    – P. Trinli
    May 6 '17 at 23:16
  • $\begingroup$ If the choice is in fact irrelevant, then I don't see any easier way of showing that than also showing what the answer is. ​ ​ $\endgroup$
    – user12859
    May 6 '17 at 23:21
  • $\begingroup$ If you generate two random strings for x and y, with finite probability your statement holds. I think. Maybe. Possibly. $\endgroup$
    – TLW
    May 8 '17 at 3:03
  • $\begingroup$ Also, I'm not sure if the concatenation changes anything, as $K(xx) \le K(x) + C$ for some constant C (dependent on the language). $\endgroup$
    – TLW
    May 8 '17 at 3:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.