Chain rule for Kolmogorov complexity: Difference between revisions

Revision as of 19:45, 11 January 2013

Revision as of 10:43, 12 January 2013

Line 21:

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

It states that the shortest program to reproduceprinting ''X'' and ''Y'' is usingobtained by concatenating a programshortest toprogram reproduceprinting ''X'' andwith a program to reproduceprinting ''Y'' given ''X'', plus [[Big-O notation|at most]] a logarithmic factor. UsingThe thisresults statementimplies onethat can define [[Mutual information#Absolute mutual information|algorithmic mutual information]], an analogue of mutual information for Kolmogorov complexity]] is symmetric.

==Proof==