<p>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.</p>

<p>Now for higher numbers of arguments, the same idea works in principle. <em>However</em>, the constant <em>does</em> 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.</p>

<p>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.</p>

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

CC BY-SA 3.0
2016-07-08T23:28:38.880Z
2016-07-08T23:28:38.880Z
Peter
<p>Due to the symmetry of information, it follows up to an additive constant that</p>

<pre><code>K(X,Y) = K(Y,X) 
</code></pre>

<p>Does this hold for more than two data objects as well? </p>

CC BY-SA 3.0
2015-07-01T12:41:06.623Z
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.
chazisop
CC BY-SA 3.0
2015-07-01T13:00:57.457Z
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.
alucard
CC BY-SA 3.0
2015-07-02T08:37:54.423Z
@RickyDemer I am considering finite set of objects.
alucard
CC BY-SA 3.0
2015-07-02T08:40:51.653Z
@RickyDemer Doesn't that mean it's a boundedly many data objects?
alucard
<cc.complexity-theory><it.information-theory><kolmogorov-complexity>
Is joint Kolmogorov Complexity order invariant?
alucard
# Is joint Kolmogorov Complexity order invariant?

(Asked by: username_0 on 2015-07-01)

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?

**Tags:** cc.complexity-theory, it.information-theory, kolmogorov-complexity

> **Comments:**
> **username_1**: 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.  
> **username_0**: 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.  
> **username_0**: @RickyDemer I am considering finite set of objects.  
> **username_0**: @RickyDemer Doesn't that mean it's a boundedly many data objects?  

---

## 1 answers

### Answer by username_2 on 2016-07-08. Score: 5 | Accepted answer

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


---

