Chain rule for Kolmogorov complexity: Difference between revisions

Revision as of 02:00, 11 February 2009

Revision as of 20:59, 3 March 2009

Line 17:

K(X,Y) = K(X) + K(Y|X) + O(\log(K(X,Y)))

</math>

(An exact version, <math>KP(X,Y) = KP(X) + KP(Y|X*) + O(1)</math>,

holds for the prefix complexty ''KP'', where ''X*'' is a shortest program for ''X''.)

It states that the shortest program to reproduce ''X'' and ''Y'' is using a program to reproduce ''X'' and a program to reproduce ''Y'' given ''X'', plus [[Big-O notation|at most]] a logarithmic factor. Using this statement one can define [[Mutual information#Absolute mutual information|an analogue of mutual information for Kolmogorov complexity]].