Złożoność Kołmogorowa

Opisowa miara informacji

Teoria Informacji Claude'a Shannona opisuje granice kompresji na podstawie statystycznych właściwości źródła danych. Entropia Shannona określa średnią ilość informacji na symbol i wyznacza teoretyczną granicę kompresji długiej wiadomości z tego źródła. Ta miara dotyczy wartości średnich i wymaga probabilistycznego modelu źródła danych.

Można też analizować pojedynczy obiekt bez budowania modelu średnich częstości. Przykładami są pierwszy rozdział powieści "Lalka" Bolesława Prusa jako konkretny ciąg znaków oraz pojedyncze cyfrowe zdjęcie kota. Takie pytania prowadzą do Algorytmicznej Teorii Informacji i jej centralnego pojęcia, czyli Złożoności Kołmogorowa. W tym ujęciu przedmiotem pomiaru jest jeden ustalony zapis, a wynik zależy od sposobu jego opisania.

Definiowanie złożoności Kołmogorowa

Rozwijana niezależnie w latach 60. XX wieku przez Andrieja Kołmogorowa, Raya Solomonoffa i Gregory'ego Chaitina, idea utożsamia złożoność obiektu z długością jego najkrótszego opisu. W świecie danych cyfrowych takim opisem może być program komputerowy. Wynik zależy od przyjętej maszyny, lecz twierdzenie o niezmienniczości ogranicza tę zależność do stałego narzutu.

Zatem formalna definicja jest następująca:

Elementy definicji

Definicję można rozłożyć na następujące elementy:

• Ciąg $s$:W tym kontekście "ciąg" może oznaczać dowolny obiekt cyfrowy. Może to być zdanie, binarny plik obrazu, sekwencja bitów pliku wykonywalnego albo pierwszy bilion cyfr liczby Pi. Jest to obiekt, którego złożoność mierzymy. Każdy taki obiekt musi mieć skończony zapis wejściowy.
• Program komputerowy $p$: Jest to program uruchamiany przez ustaloną uniwersalną maszynę. Jego długość mierzy się w bitach kodowania programu, zwykle w kodowaniu samorozdzielnym. Liczba znaków kodu źródłowego zależy od języka i nie jest definicją $K(s)$.
• Wypisuje na wyjściu ciąg $s$: Po wykonaniu program $p$ musi wygenerować ciąg $s$ jako wynik. Przyjmuje się ustalony sposób rozdzielenia programu od jego danych, aby długość opisu była jednoznaczna.
• A następnie się zatrzymuje: Program musi zakończyć obliczenie po wygenerowaniu wyniku. Warunek wiąże definicję z teorią obliczalności i Problemem Zatrzymania.
• Najkrótszy program: Istnieje wiele programów generujących dany ciąg. Program może zawierać dane i funkcję wyszukiwania albo obliczać ciąg algorytmicznie. Złożoność stanowi długość najkrótszego programu spośród tych możliwości.

Wybór języka i twierdzenie o niezmienniczości

Można by się zastanawiać, czy złożoność ciągu zależy od wybranego języka programowania. Program napisany w Pythonie może być krótszy niż równoważny program w asemblerze. Czy to oznacza, że ciąg jest "prostszy" w Pythonie?

Twierdzenie o niezmienniczości opisuje zależność od języka. Dla dwóch uniwersalnych języków programowania L1 i L2 różnica złożoności dowolnego ciągu $s$ jest ograniczona stałą zależną wyłącznie od tych języków. Można zapisać to jako $|K_{L1}(s)-K_{L2}(s)| \le c$, gdzie $c$ nie zależy od $s$. Stała może obejmować kod tłumacza oraz konwencję wejścia i wyjścia. Program tłumaczący jeden język na drugi ma stałą długość, więc jego narzut nie zależy od $s$. Dokładne wartości $K(s)$ mogą się różnić, lecz różnica pozostaje ograniczona. W analizie teoretycznej przyjmuje się zatem jedną ustaloną maszynę opisu.

Przykłady złożoności opisowej

Przykłady pokazują różnicę między wyglądem ciągu a długością jego opisu algorytmicznego.

Przykład 1: Prosty, powtarzalny ciąg

Rozważmy uporządkowany ciąg $s_1$, który składa się z litery 'A' powtórzonej 1000 razy.

Można go wygenerować programem, który zawiera cały ciąg:

Pełny zapis 1000 liter wymaga około 1000 znaków danych i nie daje skrócenia opisu. Krótszy program może użyć pętli:

Dla ustalonej wartości 1000 program jest krótki względem literalnego zapisu, więc ciąg $s_1$ ma niską złożoność Kołmogorowa, $K(s_1) \ll 1000$. Dla rodziny ciągów o postaci $A^n$ opis musi dodatkowo zakodować parametr $n$, dlatego jego długość obejmuje również bity potrzebne do zapisania wybranej wartości $n$. Wspólna reguła nadal daje krótki opis algorytmiczny, a koszt zakodowania licznika rośnie znacznie wolniej niż długość literalnego ciągu.

Przykład 2: Ciąg o wysokiej złożoności

Rozważmy ciąg $s_2$o tej samej długości 1000 znaków, otrzymany przez 1000 rzutów symetryczną monetą, na przykład z wynikami 'OROROR...'.

Wynik pojedynczego losowania może nie zawierać krótkiej reguły. Typowy wynik 1000 rzutów ma wysoką złożoność z dużym prawdopodobieństwem, lecz sam sposób jego uzyskania nie dowodzi, że konkretny ciąg jest nieskompresowalny. Jeśli nie znajdujemy krótkiego opisu, najbardziej bezpośrednim opisem pozostaje sam ciąg:

Dla typowego wyniku długość najkrótszego programu jest zbliżona do długości ciągu, więc można użyć przybliżenia $K(s_2) \approx 1000$. Ciąg, którego złożoność jest bliska długości, określa się jako algorytmicznie losowy lub nieskompresowalny względem przyjętej maszyny. Taki ciąg nie ma krótszego opisu w rozważanym modelu. Pojedyncze wyniki mogą jednak zawierać przypadkowe regularności, więc klasyfikacja dotyczy konkretnego ciągu i wybranej stałej tolerancji.

Przykład 3: Cyfry liczby Pi

Rozważmy trzeci ciąg, $s_3$, który zawiera pierwszy milion cyfr stałej matematycznej Pi.

W obliczonych próbkach cyfry wyglądają na rozmieszczone z częstościami zbliżonymi do równych i nie tworzą prostych wzorców. Taki wygląd nie stanowi dowodu równomiernego rozkładu całego rozwinięcia. Miara statystyczna, taka jak entropia Shannona, może dla przyjętego modelu wskazać wysoką zawartość informacyjną, podobną do ciągu losowego.

Pi jest precyzyjnie zdefiniowaną i obliczalną stałą matematyczną. Algorytmy, takie jak algorytm Chudnovsky'ego lub wzór Baileya-Borweina-Plouffe'a, pozwalają obliczać jej cyfry. Program implementujący jeden z nich może być znacznie krótszy niż lista cyfr.

Program zawiera algorytm oraz parametr $n$, więc jego opis nie rośnie proporcjonalnie do liczby cyfr. Dla miliona cyfr implementacja może mieć kilka kilobajtów, zależnie od języka i modelu maszyny, czyli znacznie mniej niż milion znaków ciągu. Parametr określający liczbę żądanych cyfr także musi zostać zakodowany. Dlatego ciąg $s_3$ ma krótki opis względem swojej długości, mimo losowego wyglądu.

Złożoność Kołmogorowa a entropia Shannona

Obie miary opisują inne własności danych.

Przykład cyfr Pi pokazuje tę różnicę. Entropia Shannona opisuje statystyki cyfr w przyjętym modelu, a złożoność Kołmogorowa opisuje długość programu generującego konkretny prefiks. Entropia zależy od rozkładu źródła, natomiast $K(s)$ dotyczy jednego wyniku. Złożoność Kołmogorowa dostarcza innego kryterium, lecz jej dokładna wartość jest nieobliczalna.

Nieobliczalność złożoności

Nie można zbudować kompresora, który dla każdego pliku znajdzie najkrótszy program. Złożoność Kołmogorowa ciągu jest nieobliczalna.

Fakt ten wynika z Problemu Zatrzymania, wyniku teorii obliczalności przypisywanego Alanowi Turingowi. Nie istnieje ogólny algorytm, który dla dowolnego programu i danych wejściowych określi, czy program się zatrzyma, czy będzie działał bez końca. Wyszukiwanie najkrótszego programu wymagałoby właśnie takich rozstrzygnięć dla programów, które jeszcze nie zakończyły pracy.

Aby oszacować $K(s)$, można generować programy od najkrótszych i sprawdzać ich wyniki. Program, który generuje $s$ i się zatrzymuje, daje górne ograniczenie $K(s)$. Gdy inny program działa przez minutę, godzinę lub rok, nie wiadomo, czy zakończy obliczenie, czy pozostaje w pętli. Bez rozstrzygnięcia Problemu Zatrzymania nie można wykluczyć krótszego programu ani potwierdzić optymalności znalezionego opisu.

Znaczenie praktyczne i granica teoretyczna

Nieobliczalność złożoności nie ogranicza jej roli jako pojęcia porównawczego dla kompresji. Pozwala precyzyjnie sformułować pytanie o najkrótszy opis, nawet gdy praktyczny algorytm może znaleźć tylko przybliżenie. Maszyna i konwencja kodowania należą do definicji, więc zmiana któregoś z tych elementów zmienia stałą addytywną. Przy porównywaniu koderów trzeba uwzględnić nagłówki oraz informacje pomocnicze wymagane przez dekoder.

• Definiowanie Granicy: Dostarcza teoretycznego punktu odniesienia dla kompresji bezstratnej. Dla ustalonego dekodera długość opisu zawierającego plik nie może zejść poniżej $K(s)$ z dokładnością do stałej opisującej ten dekoder. Wyznacza to granicę możliwych skróceń. Konkretna implementacja może podać tylko górne ograniczenie, ponieważ dostarcza jeden znaleziony program.
• Kierowanie Projektowaniem Algorytmów: ZIP, PNG i FLAC wykorzystują określone, obliczalne techniki, takie jak wyszukiwanie powtórzeń i modelowanie statystyczne. Nie przeszukują wszystkich programów. Algorytm jest skuteczniejszy dla danego zbioru danych, gdy znajduje krótszy opis przy zachowaniu poprawnego dekodowania. Wynik zawiera też nagłówki, słownik lub model potrzebny dekoderowi, więc porównuje się pełny opis wraz z treścią strumienia.
• Formalizowanie Losowości: Daje formalne kryterium losowości algorytmicznej. Ciąg jest algorytmicznie losowy, gdy jego złożoność jest bliska długości, z uwzględnieniem stałej zależnej od maszyny. Pojęcie to stosuje się w analizie obliczalności i informacji.

Złożoność Kołmogorowa opisuje pojedynczy obiekt przez długość najkrótszego programu, przy czym wartość zależy od ustalonej maszyny z dokładnością do stałej. Jej nieobliczalność uniemożliwia dokładne wyznaczenie dla dowolnego ciągu. Poszukiwanie krótszych poprawnych opisów pozostaje użytecznym punktem odniesienia dla kompresji bezstratnej, ponieważ każdy praktyczny koder wybiera opis z określonej klasy programów.