Chain rule for Kolmogorov complexity: Difference between revisions

Revision as of 10:43, 12 January 2013

Revision as of 10:51, 12 January 2013

Line 15:

:<math>

K(Xx,Yy) = K(Xx) + K(Yy|Xx) + O(\log(K(Xx,Yy)))

</math>

(An exact version, ''KP''(''Xx'',&nbsp;''Yy'')&nbsp;=&nbsp;''KP''(''Xx'')&nbsp;+&nbsp;''KP''(''Yy''|''Xx''*)&nbsp;+&nbsp;O(1),

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

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: ''I(x:y) = I(y:x) + O(log K(x,y))'' for all ''x,y''.

==Proof==

Line 63:

| pages = 662-664

| year = 1968 }}

* {{cite article

| coauthors = A. Zvonkin

| coauthors = L. Levin

| title = The complexity of finite objects and the development of the concepts of information and randomness by means of the theory of algorithms.

| journal = Russian Mathematical Surveys

| volume = 25

| number = 6

| pages = 83-124

| year = 1970}}