Równoważność definicji złożoności Kołmogorowa

Istnieje wiele sposobów definiowania złożoności Kołmogorowa i zwykle wszystkie te definicje są równoważne do stałej addytywnej. To znaczy, jeśli $K_1$ i $K_2$ są funkcjami złożoności Kołmogorowa (zdefiniowanymi za pomocą różnych języków lub modeli), wówczas istnieje stała $c$ taka, że dla każdego łańcucha $x$ , $|K_1(x) - K_2(x)| < c$ . Uważam, że dzieje się tak, ponieważ dla każdej funkcji złożoności Kołmogorowa $K$ i dla każdego $x$ to utrzymuje $K(x) \le |x| +c$ , dla niektórych stałych $c$ .

Interesują mnie następujące definicje $K$ , oparte na maszynach Turinga

liczba stanów : Zdefiniuj $K_1(x)$ aby była minimalną liczbą $q$ tak, że TM ze stanami $q$ wyprowadza $x$ na pustym ciągu.
$K_2(x)$ $x$ $M$ $\langle M \rangle$ $K_2(x) = \min |\langle M \rangle|$ $M$ $x$

Czy $K_1$ i $K_2$ równoważne? Jaka jest relacja między nimi, a która lepiej rozumie złożoność Kołmogorowa, jeśli nie są one równoważne.

To, co szczególnie mnie wkurza, to wzrost $K_2$ przy $x$ , który wydaje się nie być superliniowy (lub przynajmniej liniowy ze stałą $C>1$ taką, że $K_2 < C|x|$ , a nie $|x|+c$ ). Rozważ najprostszą TM, która generuje $x$ - tę, która właśnie koduje $x$ jako część funkcji stanów i przejść. od razu widać, że $K_1(x) \le |x|+1$ . Jednak kodowanie tej samej maszyny jest znacznie większe, a trywialne ograniczenie, które otrzymuję, to $K_2(x) \le |x|\log |x|$ .

computability kolmogorov-complexity

— Ran G.
źródło

Istnieje więcej niż

2^{n^{2}}

$2^{n^2}$ maszyn ze stanami

n

$n$ , a ich średni rozmiar wynosi co najmniej

n^{2}

$n^2$ , dlatego jest mało prawdopodobne, aby różniły się one jedynie stałą addytywną.

— Kaveh

Istnieje dobrze znana granica, żedla niektórych stałych niezależnych od . Jest tak, ponieważ możemy zakodować w języku bez prefiksów, po prostu podwajając każdy bit a następnie kończąc na . To zajmuje bity do reprezentowania . Ponieważ jest zdefiniowane w kategoriach uniwersalnej maszyny bez prefiksów, dla niektórych stałych . Można to poprawić, używając bardziej inteligentnego sposobu kodowania w języku wolnym od prefiksów.

K_{2} (x) \leq c + 2 | x |

$K_2(x) \leq c + 2|x|$

c

$c$

x

$x$

x

$x$

x

$x$

01

$01$

2 | x | + 2

$2|x| + 2$

x

$x$

K_{2}

$K_2$

K_{2} (x) \leq 2 | x | + 2 + c^{'}

$K_2(x) \leq 2|x| + 2 + c'$

c

$c$

x

$x$

— Carl Mummert

Nie widzę jak. Wygląda na to, że albo jest podawany jako część kodowania (jako surowe dane), albo musisz zbudować za pomocą maszyny stanów. Pierwsza opcja wydaje się oszukiwać i nie rozumiem, jak można ją porównać do drugiej opcji (co implikuje )

x

$x$

x

$x$

K_{1}

$K_1$

— Ran G.

@Ran G .: Kluczowym punktem jest twierdzenie o niezmienniczości opisane na en.wikipedia.org/wiki/Invariance_theorem . Jeśli potrafię opisać jakikolwiek skuteczny system, który ma tempo wzrostuwtedy uniwersalna maszyna Turinga (jak dla ) spełni to w ramach stałej addytywnej. Maszyna uniwersalna to taka, która pobiera są wprowadzane i zwraca wynik jeśli zatrzyma.

2 | x |

$2|x|$

K_{2}

$K_2$

⟨ M ⟩

$\langle M\rangle$

M

$M$

M

$M$

— Carl Mummert

Z góry przepraszam za to, że podam zbyt wiele szczegółów, ale mam zamiar zaprzeczyć ludziom.

O $K(x)≤K'(x)+c$

Fakt, że zwykle pochodzi z tłumacza języka opisu nr 2 na język opisu nr 1, a nie z tłumaczenia z programów nr 2 na programy nr 1. $K_1(x)≤K_2(x)+c$

Na przykład i otrzymujesz tę nierówność tak prosto jak to: $K_\mathtt{C}(x)≤K_\mathtt{Python}(x)+c_\mathtt{py2c}$

void py_run(char * s) {
    // code of your Python interpreter
}

int main(void) {
    py_run("Put here your Python program of size Kpython(x)");
}

Wtedy twoja stała będzie wynosić coś w rodzaju gdzie to liczba bitów dla tego kodu, a bitów to rozmiar, jaki oficjalny interpreter napisał w języku C. Oczywiście musisz tylko zinterpretować, co jest możliwe w języku opisu dla Pythona, dzięki czemu możesz zrobić lepiej niż 69 MB :-) $c_\mathtt{py2c}$ $528+490240688$ $528$ $490240688$

Ważne jest, abyś mógł pisać program Python liniowo w kodzie C. Na przykład język, w którym należy wstawić „BANANA” między każdą ze znaków, nie jest bardzo dobrym programem opisu, a właściwość jest wówczas fałszywa. (Ale jeśli język opisu upoważnia do zapisywania danych w osobnym pliku lub bloku, problem ten znika)

Dlaczego twój jest wadliwy $K_1(x)=q$

Problem z twoją definicją polega na tym, że możesz potrzebować więcej niż bitów, aby opisać maszynę Turinga ze stanami , ponieważ musisz zakodować przejścia. $K_1$ $q$ $q$

Więc żadne i prawdopodobnie nie są równoważne, ale to głównie wina . Myślę, że możemy udowodnić, że dla wszystkich istnieje takie, że . Oczywiście każdy wystarcza, aby obalić fakt, że nie jest prawidłową funkcją, ponieważ oznaczałoby to, że możemy zakodować więcej wszystkich możliwych ciągów długości do bitów . $K_1$ $K_2$ $K_1$ $a>0$ $c_a$ $K_1(x)≤a|x|+c_a$ $a<1$ $K_1$ $2^n$ $n$ $an+c_a$

Ale rozmiar jest niezwykle ciasno związany przy budowie maszyn Turinga. Chodzi o to, że w bloku stwierdza istnieją sposobów na znalezienie przejścia dla każdego stanu i tak lepiej niż zwykłe sposobów można wypełnić bitów. Następnie możesz przechowywać w każdym bloku bity informacji. (nie ponieważ musisz wejść i wyjść z bloku w taki czy inny sposób) $b$ $b^{2b}$ $2^b$ $b$ $\log_2 b$ $2\log_2 b$

Więc tak ... Przy blokach wielkości prawdopodobnie możesz udowodnić . Ale już napisałem zbyt wiele o tym, dlaczego liczba stanów nie jest prawidłową funkcją złożoności Kołmogorowa. Jeśli chcesz, żebym to rozwinął, zrobię to. $2^{1/a}$ $K_1(x)≤a|x|+c_a$

Teraz o $K_2$

Naiwny język opisowy odpowiada mniej więcej (tzn. dla każdego następnego stanu i szczegółów dotyczących zapisu i zakończenia). $K_2(x)=q\cdot 2 \cdot (\log_2 q + 2)$ $\log_2q$

Jak się wydaje, jestem przekonany, że lepszym / oszukańczym sposobem byłoby upoważnienie do kodowania „danych” na maszynie Turinga, być może poprzez dodanie binarnego znacznika w języku opisu, który mówi, czy stan jest stanem danych ( to po prostu pisze i przechodzi do następnego stanu) lub jeśli robi coś innego. W ten sposób możesz przechowywać jeden bit w jednym bicie twojego języka opisowego. $x$

Jeśli jednak ten sam możesz użyć tej samej techniki, której użyłem w poprzedniej części, aby zapisać kilka bitów, ale wydaje mi się, że utknąłem na (dla dowolne ) .. może mniej niż, nawet, ale uzyskanie wydaje się trudne. (I spodziewam się, że powinien to być , nawet .) $K_2$ $K_2(x)≤a|x|\log|x|+c$ $a>0$ $\log|x|$ $O(|x|)$ $|x|$ $O(|x|)$

— jmad
źródło

Ci twierdzą, że nie jest funkcją złożoności Kołmogorowa? Jest to dla mnie bardzo zaskakujące, ponieważ jest w rzeczywistości definicją stosowaną w pewnym kursie wstępu do obliczalności, który kiedyś podjąłem (nie dlatego, że mówi coś o jego poprawności).

K_{1}

$K_1$

K_{1}

$K_1$

— Ran G.

Cóż, fakt, że jest dość niepokojący. Zastanów się: istnieją możliwych słów bitów i możesz je zakodować za pomocą bitów ? Oznaczałoby to (twoje kodowanie musi być iniekcyjne)

K_{1} (x) \leq \frac{1}{2} | x | + c

$K_1(x)≤\frac12|x|+c$

2^{n}

$2^n$

n

$n$

\frac{1}{2} n + c

$\frac12n+c$

2^{n} = O (2^{\frac{1}{2} n})

$2^n=O(2^{\frac12n})$

— jmad

Co się stanie, jeśli program python ma znaki zastrzeżone przez C?

— PyRulez,

Równoważność definicji złożoności Kołmogorowa

OK(x)≤K′(x)+cK(x)≤K′(x)+cK(x)≤K'(x)+c

Dlaczego twój jest wadliwyK1(x)=qK1(x)=qK_1(x)=q

Teraz oK2K2K_2

O $K(x)≤K'(x)+c$

Dlaczego twój jest wadliwy $K_1(x)=q$

Teraz o $K_2$