Chain Rule For Kolmogorov Complexity - Proof

Proof

The ≤ direction is obvious: we can write a program to produce x and y by concatenating a program to produce x, a program to produce y given access to x, and (whence the log term) the length of one of the programs, so that we know where to separate the two programs for x and y|x (log(K(x, y)) upper-bounds this length).

For the ≥ direction, it suffices to show that for all k,l such that k+l = K(x,y) we have that either

Consider the list (a₁,b₁), (a₂,b₂), ..., (a_e,b_e) of all pairs (a,b) produced by programs of length exactly K(x,y) . Note that this list

• contains the pair (x,y),
• can be enumerated given k and l (by running all programs of length K(x,y) in parallel),
• has at most 2K(x,y) elements (because there are at most 2n programs of length n).

First, suppose that x appears less than 2l times as first element. We can specify y given x,k,l by enumerating (a₁,b₁), (a₂,b₂), ... and then selecting (x,y) in the sub-list of pairs (x,b). By assumption, the index of (x,y) in this sub-list is less than 2l and hence, there is a program for y given x,k,l of length l + O(1). Now, suppose that x appears at least 2l times as first element. This can happen for at most 2K(x,y)-l = 2k different strings. These strings can be enumerated given k,l and hence x can be specified by its index in this enumeration. The corresponding program for x has size k + O(1). Theorem proved.