Reguła łańcuchowa dla złożoności Kołmogorowa

Reguła łańcuchowa dla złożoności Kołmogorowa jest odpowiednikiem reguły łańcuchowej dla entropii informacyjnej , która stwierdza:

${\ Displaystyle H (X, Y) = H (X) + H (Y | X)}$

Oznacza to, że połączona losowość dwóch sekwencji X i Y jest sumą losowości X plus losowość Y , gdy znamy X . Wynika to bezpośrednio z definicji warunkowej i łącznej oraz z rachunku prawdopodobieństwa , że ​​prawdopodobieństwo łączne jest iloczynem prawdopodobieństwa krańcowego i warunkowego :

${\ Displaystyle P (X, Y) = P (X) P (Y | X)}$

${\ Displaystyle \ Strzałka w prawo \ log P (X, Y) = \ log P (X) + \ log P (Y | X)}$

Równoważne stwierdzenie dotyczące złożoności Kołmogorowa nie jest dokładnie prawdziwe; jest to prawdziwe tylko do logarytmicznego :

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

(Dokładna wersja, KP ( x , y ) = KP ( x ) + KP ( y | x *) + O(1), obowiązuje dla złożoności przedrostka KP , gdzie x* jest najkrótszym programem dla x .)

Stwierdza, że ​​najkrótszy program drukujący X i Y jest uzyskiwany przez połączenie najkrótszego programu drukującego X z programem drukującym Y przy danym X plus co najwyżej czynnik logarytmiczny. Wyniki implikują, że algorytmiczna informacja wzajemna , odpowiednik informacji wzajemnej dla złożoności Kołmogorowa, jest symetryczna: I(x:y) = I(y:x) + O(log K(x,y)) dla wszystkich x,y .

Dowód

Kierunek ≤ jest oczywisty: możemy napisać program, który tworzy x i y , łącząc program tworzący x , program produkujący y mając dostęp do x i (stąd logarytm) długości jednego z programów, więc że wiemy, gdzie oddzielić dwa programy dla x i y | x (log( K ( x , y )) górne granice tej długości).

Dla kierunku ≥ wystarczy pokazać, że dla wszystkich k,l takich, że k+l = K(x,y) mamy, że albo

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

Lub

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

Rozważmy listę (a ₁ ,b ₁ ), (a ₂ ,b ₂ ), ..., (ae _, b _e ) wszystkich par (a,b) tworzonych przez programy o długości dokładnie K(x,y) [stąd K(a,b) ≤ K(x,y)]. Zwróć uwagę, że ta lista

• zawiera parę (x,y) ,
• można policzyć mając dane k i l (uruchamiając równolegle wszystkie programy o długości K(x,y) ),
• ma co najwyżej 2 ^K(x,y) elementów (ponieważ jest co najwyżej 2 ⁿ programów o długości n).

Po pierwsze, załóżmy, że x pojawia się mniej niż 2 ^l razy jako pierwszy element. Możemy określić y dla danych x,k,l wyliczając (a ₁ ,b ₁ ), (a ₂ ,b ₂ ), ... a następnie wybierając (x,y) z podlisty par (x,b ) . Z założenia indeks (x,y) w tej podliście jest mniejszy niż 2 ^l , a więc istnieje program dla y danych x,k,l o długości l + O(1) . Załóżmy teraz, że x pojawia się co najmniej 2 ^l razy jako pierwszy element. Może się to zdarzyć dla co najwyżej 2 ^K(x,y)-l = 2 ^k różnych strun. Ciągi te mogą być wyliczane przy danych k, l , a zatem x można określić za pomocą jego indeksu w tym wyliczeniu. Odpowiedni program dla x ma rozmiar k + O(1) . Twierdzenie udowodnione.

•   Li, Ming; Vitányi, Paul (luty 1997). Wprowadzenie do złożoności Kołmogorowa i jej zastosowań . Nowy Jork: Springer-Verlag . ISBN 0-387-94868-6 .

•   Kołmogorow, A. (1968). „Logiczne podstawy teorii informacji i teorii prawdopodobieństwa”. Transakcje IEEE dotyczące teorii informacji . Instytut Inżynierów Elektryków i Elektroników (IEEE). 14 (5): 662–664. doi : 10.1109/tit.1968.1054210 . ISSN 0018-9448 .

•   Zvonkin, AK; Levin, Los Angeles (1970-12-31). „Złożoność obiektów skończonych i rozwój koncepcji informacji i przypadkowości za pomocą teorii algorytmów”. Rosyjskie ankiety matematyczne . Wydawnictwo IOP. 25 (6): 83–124. Bibcode : 1970RuMaS..25...83Z . doi : 10.1070/rm1970v025n06abeh001269 . ISSN 0036-0279 .