Chain rule for Kolmogorov complexity: Difference between revisions

Revision as of 16:10, 2 December 2009

Revision as of 16:11, 2 December 2009

Line 29:

that we know where to separate the two programs for ''x'' and ''y''|''x'' (log(''K''(''x'', ''y'')) upper-bounds this length).

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

construction of the set <math>A = \{(u,z) : K(u,z) \le K(x,y)\}</math>; that is, the

construction of the set of all pairs <math>(u,z)</math> such that the shortest input (for