Revision as of 18:31, 4 March 2010 edit 132.206.52.170 (talk) →References ← Previous edit		Revision as of 05:29, 11 November 2010 edit undo Tabletop (talk \| contribs) Extended confirmed users, Pending changes reviewers 177,774 edits m Spell complexty => complexity (1) Next edit →
Line 19: (An exact version, ''KP''(''X'', ''Y'') = ''KP''(''X'') + ''KP''(''Y''\|''X'') + O(1), holds for the prefix ~~complexty~~complexity ''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]].

Chain rule for Kolmogorov complexity: Difference between revisions