Kedjeregel för Kolmogorovs komplexitet

Kedjeregeln för Kolmogorovs komplexitet är en analog till kedjeregeln för informationsentropi , som säger:

$H(X,Y)=H(X)+H(Y|X)$

Det vill säga, den kombinerade slumpen av två sekvenser X och Y är summan av slumpmässigheten av X plus den slumpmässighet som finns kvar i Y när vi väl känner till X . Detta följer omedelbart av definitionerna av villkorlig och gemensam entropi , och faktumet från sannolikhetsteorin att den gemensamma sannolikheten är produkten av den marginella och villkorade sannolikheten :

$P(X,Y)=P(X)P(Y|X)$

$\Rightarrow \log P(X,Y)=\log P(X)+\log P(Y|X)$

Motsvarande uttalande för Kolmogorovs komplexitet håller inte exakt; det är sant endast upp till en logaritmisk term:

$K(x,y)=K(x)+K(y |x)+O(\log(K(x,y)))$

(En exakt version, KP ( x , y ) = KP ( x ) + KP ( y | x *) + O(1), gäller för prefixkomplexiteten KP , där x* är det kortaste programmet för x .)

Den anger att den kortaste programutskriften X och Y erhålls genom att sammanfoga en kortaste programutskrift X med en programutskrift Y givet X plus som mest en logaritmisk faktor. Resultaten antyder att algoritmisk ömsesidig information , en analog av ömsesidig information för Kolmogorovs komplexitet, är symmetrisk: I(x:y) = I(y:x) + O(log K(x,y)) för alla x,y .

Bevis

≤-riktningen är uppenbar: vi kan skriva ett program för att producera x och y genom att sammanfoga ett program för att producera x , ett program för att producera y med tillgång till x , och (därav loggtermen) längden på ett av programmen, så att vi vet var vi ska separera de två programmen för x och y | x (log( K ( x , y )) övre gränsen för denna längd).

För ≥-riktningen räcker det att visa att för alla k,l så att k+l = K(x,y) har vi att antingen

K(x|k,l) ≤ k + O(1)

eller

K(y|x,k,l) ​​≤ 1 + O(1) .

Betrakta listan (a ₁ ,b ₁ ), (a ₂ ,b ₂ ), ..., (a _e ,b _e ) av alla par (a,b) som produceras av program med längden exakt K(x,y) [därav K(a,b) ≤ K(x,y)]. Observera att denna lista

• innehåller paret (x,y) ,
• kan räknas upp givet k och l (genom att köra alla program med längden K(x,y) parallellt),
• har högst 2 ^K(x,y) element (eftersom det finns högst 2 ⁿ program med längden n).

Antag först att x visas mindre än 2 ^l gånger som första element. Vi kan specificera y givet x,k,l genom att räkna upp (a ₁ ,b ₁ ), (a ₂ ,b ₂ ), ... och sedan välja (x,y) i underlistan med par (x,b) ) . Genom antagande är indexet för (x,y) i denna dellista mindre än 2 ^l och därför finns det ett program för y givet x,k,l med längden l + O(1) . Antag nu att x visas minst 2 ^l gånger som första element. Detta kan hända för högst 2 ^K(x,y)-l = 2 ^k olika strängar. Dessa strängar kan räknas upp givet k,l och därför kan x specificeras av dess index i denna uppräkning. Motsvarande program för x har storleken k + O(1) . Teorem bevisat.

•   Li, Ming; Vitányi, Paul (februari 1997). En introduktion till Kolmogorovs komplexitet och dess tillämpningar . New York: Springer-Verlag . ISBN 0-387-94868-6 .

•   Kolmogorov, A. (1968). "Logisk grund för informationsteori och sannolikhetsteori". IEEE-transaktioner på informationsteori . Institutet för el- och elektronikingenjörer (IEEE). 14 (5): 662–664. doi : 10.1109/tit.1968.1054210 . ISSN 0018-9448 .

•   Zvonkin, AK; Levin, LA (1970-12-31). "Komplexiteten hos finita objekt och utvecklingen av begreppen information och slumpmässighet med hjälp av teorin om algoritmer". Ryska matematiska undersökningar . IOP-publicering. 25 (6): 83–124. Bibcode : 1970RuMaS..25...83Z . doi : 10.1070/rm1970v025n06abeh001269 . ISSN 0036-0279 .