Przybliżenie złożoności Kołmogorowa

Studiowałem coś na temat złożoności Kołmogorowa , przeczytałem kilka artykułów i książek Vitanyi i Li i wykorzystałem koncepcję znormalizowanej odległości kompresji, aby zweryfikować stilometrię autorów (określić, w jaki sposób każdy autor pisze niektóre dokumenty tekstowe i grupowe według ich podobieństwa).

W takim przypadku zastosowano kompresory danych w celu przybliżenia złożoności Kołmogorowa, ponieważ kompresor danych można wykorzystać jako maszynę Turinga.

Oprócz kompresji danych i języków programowania (w których napisałbyś jakiś kompresor), czego jeszcze można by użyć do przybliżenia złożoności Kołmogorowa? Czy można zastosować jakieś inne podejście?

Chyba jedna z możliwych odpowiedzi na to pytanie jest taka: Weź generator liczb pseudolosowych . Spróbuj wybrać generator, który ma kilka potężnych ataków przeciwko niemu: atak generatora liczb losowych dla G jest (dla naszych celów), algorytmem A, który po podaniu ciągu imputacyjnego s określa ziarno A ( s ) , takie że G ( A ( s ) ) = s . Następnie przybliż KC s :$G$$G$$A$$s$ $A(s)$$G(A(s))=s$$s$

input: s
Compute A(s);
if |A(s)| + |G| > |s| output: |s|
otherwise output: |A(s)| + |G|

Gdzie to długość programu obliczającego G ( s ) (często dość krótki, jak w przypadku generatorów liniowych).$|G|$$G(s)$

Należy zauważyć, że w praktyce ataki generatora liczb losowych są niezgodne z opisem: mogą zawieść lub spowodować niepełne wyniki. W takim przypadku możesz dostosować algorytm, aby zwracał gdy wynik ataku jest niezadowalający. Ta sama uwaga dotyczy algorytmów kompresji.$|s|$

Zastrzeżeniem tego podejścia, w przeciwieństwie do algorytmów kompresji, jest to, że algorytmy kompresji są zasadniczo znacznie bardziej odpowiednie do obliczania KC, ponieważ są dostosowane do pracy na dowolnym łańcuchu, podczas gdy atak może działać tylko wtedy, gdy jest na obrazie G ( bardzo mało prawdopodobne ).$s$$G$

$p(x)$$-\log p(x)$

To dlatego złożoność Kołmogorowa jest tak interesująca, nie dlatego, że jest to ostateczny algorytm kompresji (i tak zależy na kompresji), ale dlatego, że jest to najlepszy algorytm uczenia się . Kompresja i uczenie się to w zasadzie to samo: znajdowanie wzorców w danych. Ramy statystyczne zbudowane na tej idei nazywane są Minimalną długością opisu i zostały bezpośrednio zainspirowane złożonością Kołmogorowa.

Zobacz także to pytanie na cStheory StackExchange.

kodowanie gramatyczne jest rzadziej używaną wersją algorytmu kompresji i może być traktowane jako „przybliżona” ocena złożoności Kołmogorowa. kodowanie gramatyczne nie jest tak powszechnie stosowane jako algorytm kompresji, jak inne bardziej powszechne podejścia, być może głównie dlatego, że nie poprawia znacznie kompresji z np. Lempel-Ziv na korpusach tekstowych, ale może dobrze radzić sobie z innymi rodzajami danych. chodzi o „skompresowanie” łańcucha przy użyciu reguł gramatycznych. wyprowadzenie gramatyki może skutkować DAG (w porównaniu z mniej złożonym drzewem), więc możliwa jest znaczna złożoność reprezentacyjna.

inną opcją jest znalezienie najmniejszych / minimalnych obwodów reprezentujących łańcuch, ale wiadomo, że ma on bardzo dużą złożoność obliczeń i może odnieść sukces tylko na małych łańcuchach.

$K(x)$

$K(x)$

istnieją również inne metody algorytmu kompresji oprócz podejść typu „kodowania długości przebiegu” Lempela-Ziva, na przykład algebra wektorowa i SVD mogą być użyte jako algorytm kompresji. również transformaty Fouriera są często używane do kompresji obrazów, np. w standardzie JPG.