Oczekiwane wartości złożoności Kołmogorowa w losowej próbie

Złożoności Kołmogorowa łańcucha nie można obliczyć. Jednakże, w losowej podgrupy o rozmiarze dwuskładnikowych ciągi o długości , ile, będą miały mniejszą złożoność niż pewnej liczby całkowitej mniej niż (jako funkcja , i )?$M$$n$$n_{0}$$n$$M$$n$$n_{0}$

Złożoność Kołmogorowa jest określana tylko do pewnej stałej addytywnej, więc nie jest możliwe podanie dokładnej odpowiedzi. Granica, którą tu opisuję, jest jeszcze słabsza.

Oczywiście oczekiwanej liczby można łatwo obliczyć, gdy wiemy, ile z łańcuchów ma złożoność mniejszą niż , więc pozwól mi odpowiedzieć na to. Zazwyczaj jest to pierwsze stwierdzenie o złożoności Kołmogorowa, że ​​liczba ta wynosi co najwyżej - ponieważ istnieje tylko tyle ciągów o mniejszej długości. Z drugiej strony, jeśli twój program mówi „o długości , weź liczbę”, to otrzymasz ciągów złożoności mniejszych niż , gdzie jest wolna od prefiksów wersja złożoności Kołmogorowa wynosząca (co najwyżej$2^n$$n_0$$2^{n_0}-1$$n$$x$$2^{n_0-K(n)-C}$$n_0$$K(n)$$n$$\log n+\log^* n + O(1)$). Bardziej szczegółowo, ciąg zawiera najpierw opis maszyny Turinga, która pobrała wejściowy , gdzie p jest opisem programu bez prefiksu, który wypisuje , wypisuje tą liczbę długości , która jest bitami , a następnie następuje .$px$$n$$x$$n$$O(1)$$px$

Prawdopodobnie można poprawić te granice, ale wątpię, aby uzyskać dokładną odpowiedź.

Można podać dokładną odpowiedź. Liczba ciągów długości$n$ co najwyżej z (prostą) złożonością $n_0$ jest $2^{n_0 - K(n_0|n)}$, aż do stałego współczynnika. Stąd każdy proces, który losowo wybiera podzbiór, będzie miał, z rozsądnym prawdopodobieństwem, a$2^{-K(n_0|n) + O(1)}$ część ciągów złożoności mniejsza niż $n_0$. Aby pokazać naszą naszego twierdzenia, wystarczy pokazać, że liczba strun z złożoność równa się$k$ jest również podany przez $2^{k - K(k|n)}$. Możemy pokazać niezbędny wynik, określając sumę tej wartości$k$ od 1 do $n_0$. Aby to pokazać, używamy wyniku addytywności dla zwykłej złożoności (ze względu na B. Bauwensa i A. Shena. Twierdzenie o addytywności dla zwykłej złożoności Kołmogorowa . Teoria systemów obliczeniowych, 52 (2): 297-302, luty 2013),

$$C(a,b) = K(a|C(a,b)) + C(b|a,C(a,b)) + O(1).$$ Tutaj $K(\cdot)$oznacza złożoność Kołmogorowa bez prefiksów. Wybieranie$a = n$obserwujemy to dla każdego $n$-bitowy ciąg $b$ złożoności $k$ mamy $$k = C(b) = C(n,b) + O(1) = K(n|k) + C(b|n,k) + O(1).$$ Dlatego dla każdego takiego $b$ mamy $C(b|n,k) = k - K(n|k)+O(1)$. Pozwolić$k' = k - K(n|k)$. Teraz można zauważyć, że są co najwyżej$O(2^{k'})$ takie sznurki $b$i każdy z leksykograficznie pierwszy $2^{k'}$ sznurki długości $n$ usatysfakcjonować $C(b|n,k) \le k' + O(1)$. A zatem$\Omega(2^{k'})$ z nich spełniają $C(b|n,k) = k' + O(1)$.