Wykorzystanie złożoności Kołmogorowa jako wejściowego „rozmiaru”

$S$

$$I(n) = \{w \in S : |w| = n\}$$ $n$$T(w)$$A$$w$$A$ $$f_n = \max_{w \in I(n)} T(w).$$

Zdefiniujmy teraz zbiory wszystkich danych wejściowych o złożoności Kołmogorowa , i zdefiniujmy sekwencję Tutaj jest średnią sekwencją czasu pracy dla , z wyjątkiem przypadków, gdy „rozmiar” danych wejściowych jest złożonością Kołmogorowa, a nie ich długością.n f K n =

$$I^K(n) = \{w \in S : K(w) = n \}$$ $n$fK $$f^K_n = \frac{1}{\left|I^K(n)\right|} \sum_{w \in I^K(n)} T(w).$$ $f^K$$A$

Czy istnieją algorytmy, dla których jest asymptotycznie znacząco różne od ? Jeśli tak, to czy występują problemy, których złożoność czasowa zmienia się podczas korzystania z tego innego sposobu analizy algorytmów?f K $f_n$$f^K_n$

Rozważ funkcję parzystości (lub dowolną inną funkcję, która zależy od wszystkich / większości bitów wejścia). Dla funkcji parzystości . Więc Z drugiej strony, f n = Θ ( n ) . f K n = Θ ( $T(w) = \Theta(|w|)$

$$f_n = \Theta(n).$$ $$f_n^K = \Theta\left(\frac{1}{|I^K(n)|} \sum_{w:K(w) = n} |w|\right) \geq \Omega\left(\frac{1}{2^n} \max_{w:K(w) = n} |w|\right).$$

Zauważ, że . Zatem i . Podobnie, ; dlatego „rośnie bardzo szybko”. Co więcej, to nie trudno zauważyć, że nie jest obliczalny górna granica dla .max w : K ( w ) = n | w | ≥ 2 2 Ω ( n ) f K n ≥ 2 2 Ω ( n ) / 2 n → ∞ K ( 2 … 2 2 n ) = O ( n ) f K $K(2^{2^n}) = O(n)$

$$\max_{w:K(w) = n} |w| \geq 2^{2^{\Omega(n)}}$$ $f_n^K \geq 2^{2^{\Omega(n)}} / 2^n \to \infty$$K(2^{\dots^{2^{2^n}}}) = O(n)$f K $f_n^K \geq 2^{\dots^{2^{2^{\Omega(n)}}}}/2^n$$f_n^K$

Biorąc pod uwagę zainteresowanie tym pytaniem, pomyślałem, że bardziej pomocne może być wyraźniejsze wskazanie powodu, dla którego nie powinniśmy być wcale zaskoczeni odpowiedzią i starać się podać kierunek dla doprecyzowania pytania. To zbiera i rozwija się w przypadku niektórych komentarzy. Przepraszam, jeśli to „oczywiste”!

Rozważ zestaw ciągów złożoności Kołmogorowa : Istnieje najwyżej takich ciągów, ponieważ istnieją opisów długości . Zauważ jednak, że ten zestaw jest nierozstrzygalny dla ogólnego (w przeciwnym razie moglibyśmy obliczyć po prostu przez iterację od do i sprawdzenie członkostwa w ). Ponadto funkcja rośnie nieobliczalnie szybko. Jest to wariant funkcji bobra zajętego: jaka jest najdłuższa wydajność maszyny Turinga o długości opisu$n$

$$J^K(n) = \{w : K(w) = n\}.$$ $2^n$$2^n$$n$$n$$K(w)$$n=1$$|w|$$J^K(n)$ $$g^K(n) = \max_{w \in J^K(n)} |w|$$ $n$? Gdyby to rosło wolniej niż jakaś funkcja obliczeniowa, moglibyśmy zdecydować o problemie zatrzymania: Biorąc pod uwagę TM , konstruuj który symuluje i wypisuje na każdym kroku. Jeżeli długość opisu wynosi , to albo: zatrzymuje się co najwyżej kroków; lub nie zatrzymuje się.$M$$M'$$M$$1$$M'$$n$$M$$g^K(n)$$M$

Teraz, na pytanie Andrzeja, mamy, że , gdzie jest językiem oryginalnym. Tak więc jedynym sposobem uniknięcia zawierającego dane wejściowe bardzo duże w byłoby, gdyby zawierało tylko bardzo nieściśliwe łańcuchy. (Zauważ, że w przeciwnym razie możemy całkowicie zignorować rozróżnienie między analizą najgorszego i średniego przypadku, ponieważ uśredniamy co najwyżej ciągów, ale rozmiar największego ciągu rośnie szybciej niż jakakolwiek obliczalna funkcja . )$I^K(n) = S \cap J^K(n)$$S$$I^K(n)$$n$$S$$2^n$$n$

Wydaje mi się, że prawdopodobnie nie jest możliwe zbudowanie nietrywialnej (tj. Nieskończonej) litery która zawiera tylko nieściśliwe łańcuchy, ale jest rozstrzygalna. Ale nie wiem. Mamy jednak nadzieję, że daje to intuicję, dlaczego nie powinniśmy mieć nadziei, że w większości języków rosło wolniej niż funkcja obliczalna.$S$$f^K_n$

Aby cofnąć się nieco, pytanie polega na porównaniu wydajności na wejściach o długości do wydajności na wejściach, które można skompresować do długości . Ale mamy pojęcia kompresji, które są znacznie łatwiejsze do opanowania (i mniej skuteczne) niż złożoność Kołmogorowa. Prostym sposobem jest podanie obwodu o rozmiarze , który na wejściu liczby binarnej wytwarza ty bit . Zauważ, że tutaj powiększenie wielkości wejściowej jest co najwyżej wykładnicze (obwód o wielkości ma co najwyżej możliwych sygnałów wejściowych).$n$$n$$n$$b$$b$$w$$n$$2^n$

Możemy więc przeformułować pytanie, pozwalając I analogicznie zdefiniuj . Powodem nadziei jest to, że większość łańcuchów wymaga obwodu prawie tak dużego jak sam łańcuch i żadne łańcuchy nie są wykładniczo większe niż wymagany obwód. Być może w tym przypadku moglibyśmy znaleźć języki, w których i są podobne asymptotycznie.

$$I^C(n) = \{ w \in S : \text{the smallest circuit implicitly specifying $w$ has size $n$}\}.$$ $f^C_n$$f_n$$f^C_n$

Dość blisko spokrewnionym pytaniem jest złożoność niejawnych języków, takich jak IMPLICIT_SAT jest NEXP-zupełny, i zwykle niejawna wersja problemów NP-zupełnych jest NEXP-zupełna. Zdecydowanie IMPLICIT_SAT jest co najmniej tak proste, jak użycie obwodu do wypisania całego , a następnie uruchomienie algorytmu dla SAT na . Jeśli więc dla SAT, to wydaje się to bliskie dostarczenia dowodów, że IMPLICIT_SAT w średnim przypadku jest prawie tak szybko rozstrzygalny, jak SAT w najgorszym przypadku. Ale nie wiem, jak można by bezpośrednio porównać twoje pojęcie z domyślnymi językami, ponieważ pojęcie „najmniejszego obwodu dla

$$\mathsf{IMPLICIT\_SAT} = \{ \text{circuits $C$}: \text{$C$ implicitly specifies $w$}, w \in \mathsf{SAT}\}.$$ $w$$w$$f^C_n = \Theta(f_n)$$w$„nie wchodzi w grę dla domyślnych języków.

Mam nadzieję, że jest to pomocne / interesujące!

Nie jestem pewien podręcznika, który wspomina o ukrytych problemach, ale oto kilka notatek z wykładów: http://people.seas.harvard.edu/~salil/cs221/spring10/lec8.pdf

Łatwym przypadkiem wydaje się być to, że język zawiera tylko wyściełane wystąpienia. Gdy otrzymuje się z języka poprzez impregnowanie każde wystąpienie wielkości o symboli może być w obszarze .S L n 2 n - n f K n 2 f $S$$S$$L$$n$$2^n-n$$f^K_{n}$$2^{f_n}$