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$ 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$
    – chazisop
    Jul 1 '15 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$
    – alucard
    Jul 1 '15 at 13:00
  • $\begingroup$ Are you considering unboundedly many data objects or only boundedly many data objects? $\hspace{.38 in}$ $\endgroup$
    – user6973
    Jul 1 '15 at 17:31
  • 1
    $\begingroup$ That ... doesn't answer my question. $\;$ $\endgroup$
    – user6973
    Jul 2 '15 at 8:39
  • 1
    $\begingroup$ No, but that does answer my question. $\;$ $\endgroup$
    – user6973
    Jul 2 '15 at 8:42

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).$$


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.