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)?
6
-
$\begingroup$ What description language does your K use? $\endgroup$– user12859Commented May 6, 2017 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. TrinliCommented May 6, 2017 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$– user12859Commented May 6, 2017 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$– TLWCommented May 8, 2017 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$– TLWCommented May 8, 2017 at 3:03
|
Show 1 more comment