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}$

cc.complexity-theory kolmogorov-complexity

— vs
źródło

Czy używasz tutaj „standardowej” złożoności Kołmogorowa czy złożoności prefiksu?

— Aubrey da Cunha,

Właściwie myślałem tylko o złożoności Kołmogorowa. Zgadywałem granicę wspomnianą przez domotorp, gdy rozważamy wszechświat wszystkich łańcuchów. Nie było jasne, czy wszystkie „zgodny” wynik dla dowolnego losowego podzbioru wielkości mogą być produkowane. Czy jednak złożoność prefiksu doprowadziłaby nas do innego punktu widzenia?

2^{n_{o}}

$2^{n_{o}}$

M

$M$

— do

Z pewnością nie zmieniłoby to rzędu wielkości, w rzeczywistości myślę, że teraz moja odpowiedź jest ograniczona dla obu wersji.

— domotorp

Dla każdego i każdego prawdopodobieństwo, że losowy bitowy ciąg ma złożoność Kołmogorowa jest większy niż (przy ) . Tak więc w losowym rozkładzie ciągów należy spodziewać się ciągów z ... intuicyjnie, istnieje bardzo duże prawdopodobieństwo wybrania ciągu o wysokiej złożoności Kołmogorowa.

n

$n$

c

$c$

n

$n$

x

$x$

K (x) \geq n - c

$K(x) \geq n-c$

1 - \frac{1}{2^{c}}

$1 - \frac{1}{2^c}$

c = n - n_{0}

$c = n-n_0$

M

$M$

\frac{M}{2^{(} n - n_{0})}

$\frac{M}{2^(n-n_0)}$

K (x) < n_{0}

$K(x) \lt n_0$

— Marzio De Biasi,

Odpowiedzi:

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ź.

— domotorp
źródło

Czy mógłbyś wyjaśnić trochę zdanie „jeśli twój program mówi„ o długości n, weź x liczbę ”?

— do

Masz rację, tam powinien być prefiks, poprawiłem to.

— domotorp

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) .

$C(a,b) = K(a|C(a,b)) + C(b|a,C(a,b)) + O(1).$ Tutaj

K (\cdot)

$K(\cdot)$ oznacza złożoność Kołmogorowa bez prefiksów. Wybieranie

a = n

$a = n$ obserwujemy to dla każdego

n

$n$ -bitowy ciąg

b

$b$ złożoności

k

$k$ mamy

k = C (b) = C (n, b) + O (1) = K (n | k) + C (b | n, k) + O (1) .

$k = C(b) = C(n,b) + O(1) = K(n|k) + C(b|n,k) + O(1).$ Dlatego dla każdego takiego

b

$b$ mamy

C (b | n, k) = k - K (n | k) + O (1)

$C(b|n,k) = k - K(n|k)+O(1)$ . Pozwolić

k^{'} = k - K (n | k)

$k' = k - K(n|k)$ . Teraz można zauważyć, że są co najwyżej

O (2^{k^{'}})

$O(2^{k'})$ takie sznurki

b

$b$ i każdy z leksykograficznie pierwszy

2^{k^{'}}

$2^{k'}$ sznurki długości

n

$n$ usatysfakcjonować

C (b | n, k) \leq k^{'} + O (1)

$C(b|n,k) \le k' + O(1)$ . A zatem

Ω (2^{k^{'}})

$\Omega(2^{k'})$ z nich spełniają

C (b | n, k) = k^{'} + O (1)

$C(b|n,k) = k' + O(1)$ .

— Bruno Bauwens
źródło