Wikipedia

Chain rule for Kolmogorov complexity: Difference between revisions

Browse history interactively
← Previous edit
Content deleted Content added
VisualWikitext
fix math itaclics
Reverted 1 edit by Dragonthereal (talk): Editorializing
 
(2 intermediate revisions by 2 users not shown)
Line 26:
holds for the prefix complexity ''KP'', where {{math|''x''{{sup|∗}}}} is a shortest program for ''x''.)
 
It states that the shortest program printing ''X'' and ''Y'' is obtained by concatenating a shortest program printing ''X'' with a program printing ''Y'' given ''X'', plus [[Big-O notation|at most]] a logarithmic factor. The results implies that [[Mutual information#Absolute mutual information|algorithmic mutual information]], an analogue of mutual information for Kolmogorov complexity is symmetric: {{tmath|1=I(x:y) = I(y:x) + O(\log K(x,y))}}</font> for all ''x,y''.
 
==Proof==
Retrieved from "https://en.wikipedia.org/wiki/Chain_rule_for_Kolmogorov_complexity"