Chain rule for Kolmogorov complexity: Difference between revisions

Revision as of 19:00, 22 December 2006

Revision as of 00:00, 23 December 2006

Line 28:

access to <math>x</math>, and (whence the log term) the length of one of the programs, so

that we know where to separate the two programs for <math>x</math> and <math>y|x</math>

(</math>\log(K(x,y))</math> upper bounds this length).

The <math>\ge</math> direction is rather more difficult. The key to the proof is the

Line 73:

Now, we can enumerate a set of possible values for <math>x</math> by finding all <math>u</math> such

that <math>|A_u| > 2^e</math> -- list only the <math>u</math> such that <math>y</math> is output after more than

</math>2^e</math> other values when enumerating <math>A_u = \{ z: K(u,z) \le K(x,y) \}</math>. <math>x</math> is

one such <math>u</math>. Let <math>U</math> be the set of all such <math>u</math>. We can enumerate <math>U</math> by

enumerating each <math>A_u</math> (in parallel, as usual) and outputting a <math>u</math> only when

</math>y</math> would be output for <math>A_u</math> and more than <math>2^e</math> other values for the <math>A_u</math>

would be output. Note that given <math>K(x,y)</math>, <math>e</math> and the index of <math>x</math> in <math>U</math> we

can enumerate <math>U</math> to recover <math>x</math>.

Line 82:

Note that <math>\{(u,z) : u \in U, z \in A_u\}</math> is a subset of <math>A</math>, and <math>A</math> has at

most <math>2^{K(x,y)}</math> elements, since there are only that many programs of length

</math>K(x,y)</math>. So we have:

:<math> |U| < \frac{|A|}{2^e} \le \frac{2^{K(x,y)}}{2^e} </math>