Due to the symmetry of information, it follows up to an additive constant that
K(X,Y) = K(Y,X)
Does this hold for more than two data objects as well?
$\begingroup$
$\endgroup$
7
-
$\begingroup$ I am completely oblivious to anything but the basics of Kolmogorov Complexity, but shouldn't an inductive argument work? E.g.$ K(X,Y,Z) = K( (X,Y) , Z) = K ( Z , (X,Y) ) = K(Z,X,Y)$ I realize it might be possible to more efficiently encode X and Y together other than $(X,Y)$, but this representation is meant to have the same Kolmogorov complexity as the sum of the complexities of the two data objects. $\endgroup$– chazisopJul 1, 2015 at 12:41
-
$\begingroup$ Well your argument makes sense. But it's tricky what (X,Y) means inside K((X,Y),Z). Also I figured out that the existence of a Turing Machine which figures out the permutation of the data objects (maybe over an index of all permutations) would essentially mean that the order is invariant in Joint case. $\endgroup$– alucardJul 1, 2015 at 13:00
-
$\begingroup$ Are you considering unboundedly many data objects or only boundedly many data objects? $\hspace{.38 in}$ $\endgroup$– user6973Jul 1, 2015 at 17:31
-
1$\begingroup$ That ... doesn't answer my question. $\;$ $\endgroup$– user6973Jul 2, 2015 at 8:39
-
1$\begingroup$ No, but that does answer my question. $\;$ $\endgroup$– user6973Jul 2, 2015 at 8:42
|
Show 2 more comments
1 Answer
$\begingroup$
$\endgroup$
You don't need symmetry of information. The invariance theorem does the trick. Let $p$ the smallest program such that $U(p) = \langle x, y\rangle$. One way of producing $(y, x)$ is to take make a program $q$ that runs whatever program it is given as input, interprets the output as a pair, and flips the two parts. This gives you a program $\overline{q}p$ to produce $\langle y, x\rangle$. Since $\overline{q}$ is only a constant number of bits long, the two $K$'s are equal up to a constant.
Now for higher numbers of arguments, the same idea works in principle. However, the constant does depend on the number of arguments: if I want to write a $q$ program to compute some $n$-tuple of numbers and re-arrange it into an arbitrary order, I need to encode the order in $\log(n!)$ bits (if the ordering is random). So if the number of arguments is not fixed to a constant, you need to take that into account.
Isn't there some other way, besides the $q$ program? No, if there were we could encode free information in the ordering of the tuple.
Assume for a contradiction that $K(x_1, \ldots, x_n)$ is invariant up to a constant to permutation of the arguments, with the constant independent of $n$. Let $X = \langle x_1, \ldots, x_n\rangle$ be the enumeration of the first $n$ binary strings, so that $K(X) \leq_+ K(n)$. Let $z$ be a random string with $|z| = \log(n!)$ Let $\langle x_1, \ldots, x_n \rangle$ be a random string. Index all permutations of $n$ elements by binary strings and pick the one corresponding to $z$. Call this permutation of our tuple $X_z$. Let $p$ and $p_z$ be the shortest programs for $X$ and $X_z$ respectively. Build a program $q$ that reads input $\overline{p}p_z$ and returns $z$. Putting all this together gives us $$\log(n!) \leq_+ K(z) \leq_+ |\overline{q}\overline{p}p_z| \leq_+ 2K(X) \leq_+ 2K(n) \leq_+ 4\log(n).$$
