Czy istnieją x takie, że K (xx) <K (x), gdzie K jest złożonością Kołmogorowa.

Niech oznacza złożoność Kołmogorowa ciągu . Czy istnieje taki ciąg znaków, że . (Tutaj jest konkatenacją z samym sobą). Podobny, ale różne pytano tutaj , ale kontrprzykład podane w odpowiedzi na to pytanie nie jest dostępna dla tego jednego. $K(x)$ $x$ $K(xx)<K(x)$ $xx$ $x$

cc.complexity-theory kolmogorov-complexity

— Sune Jakobsen
źródło

Odpowiedzi:

Nie jestem ekspertem od złożoności Kołmogorowa, ale myślę, że takie x można zbudować dla każdej funkcji złożoności K w następujący sposób. Ponieważ 1, 11, 1111, 11111111,…, 1 ^{2 ⁿ} ,… jest kodowaniem liczby naturalnej n , K (1 ^{2 ⁿ} ) nie może być o (log n ). Jednak gdy n = 2 ^m , oczywiście K (1 ^{2 ⁿ} ) = K (1 ^{2 ^{2 ^m}} ) = O (log m ) = O (log log n ). Dlatego sekwencja K (1), K (11), K (1111), K (11111111),…, K ( ^{12 ⁿ} ),… nie może być słabo monotonicznie rosnąca, co oznacza, że istnieje strunaxw postaci 1 ^{2 ⁿ} takiej, że K ( xx ) <K ( x ).

— Tsuyoshi Ito
źródło

@Tsuyoshi, Czy istnieje ciąg nieściśliwy

taki, że

x

$x$

K (x x) < K (x)

$K(xx)\lt K(x)$

— Mohammad Al-Turkistany

Myślę, że

i K (1 ^ {2 ^ n}) = Ω (log n) są ze sobą sprzeczne. Ma na myśli: jeśli

. W przeciwnym razie dowód wydaje się w porządku.

K (1^{2^{2^{m}}}) = O (\log m)

$K(1^{2^{2^m}})=O(\log m)$

f (n) = o (\log n)

$f(n)=o(\log n)$

K (1^{2^{n}}) \neq O (f (n))

$K(1^{2^n})\neq O(f(n))$

— Sune Jakobsen,

To wydaje się działać. Rzeczywiście, myślę, że daje to nieskończoną sekwencję takich ciągów. Jednak albo coś źle rozumiem, albo stwierdzenie reguły łańcuchowej dla złożoności Kołmogorowa, które pojawia się w wikipedii ( en.wikipedia.org/wiki/Chain_rule_for_Kolmogorov_complexity ) jest wtedy błędne. Początkowo myślałem, że definicja wikipedii może tutaj nie mieć zastosowania, ponieważ musisz wiedzieć, gdzie kończy się X, a Y zaczyna, podczas gdy tutaj wydaje się, że nie jest to wymagane, ale gdy Y = X możesz dodać to do opisu w O (1) mówiąc „rozdzielić na środku”.

— Abel Molina

@Sune: Notacja Ω (⋅) ma kilka nieco różnych definicji. „K (1 ^ 2 ^ n) = Ω (log n)” w mojej odpowiedzi oznacza „limsup K (1 ^ 2 ^ n) / log n> 0” i nie jest sprzeczne z „K (1 ^ 2 ^ 2 ^ m) = O (log m). ”Zredagowałem odpowiedź, aby wyjaśnić ten punkt. Zobacz także Jakiej definicji asymptotycznej stopy wzrostu powinniśmy uczyć?

— Tsuyoshi Ito

@turkistany i wszyscy: Zauważ, że zawsze jest prawdą, że K (xx)> K (x) -c dla jakiejś stałej, pomyślałem, że należy to zaznaczyć. Oznacza to również, że potrzebujemy bardzo dokładnej definicji nieściśliwości, jeśli chcemy przestudiować to pytanie. Sądzę, że odpowiedź brzmi: tak, ale nie mam dowodu.

— domotorp

Tak. Złożoność Kołomogorowa w praktyce zależy od modelu. Maszyna Turinga, program Java, program C ++, ... jeśli w twoim modelu jest pewna specyfika, która pozwala na to w przypadku skończonego zestawu danych wejściowych, nie ma problemu.

Lepszym pytaniem jest, jak wiele z tego zachowania można uniknąć i nadal mieć uniwersalny model.

— Chad Brewbaker
źródło

Myślę, że lepszym pytaniem jest: czy takie x istnieje dla wszystkich modeli? Nie wiem, czym jest „model”, ale wydaje się, że odpowiedź Tsuyoshisa działa we wszystkich rozsądnych językach programowania.

— Sune Jakobsen,

Możesz przypisać

i coś większego dla

i nadal mieć model uniwersalny.

0

$0$

x x

$xx$

x

$x$

— Kaveh

@Tsuyoshi:

Nie zrozumiałem dobrze twojego dowodu.

$K(s)$ $s$

$TM_{ss}$ $ss = 1111...1 = 1^{2^{n+1}}$ $TM_{s}$ $s = 1^{2^n}$

Czy twój dowód można zastosować do złożoności Kołmogorowa na bazach TM?

$n+1 = 2^{m}$ $TM_{ss}$ $TM_{s}$ $n$

(przepraszam, ale nie wiem jak to opublikować jako komentarz)

— Marzio De Biasi
źródło

Aby napisać komentarz do posta napisanego przez kogoś innego niż ty, który nie jest odpowiedzią na twoje pytanie, potrzebujesz punktu reputacji co najmniej 50.

— Tsuyoshi Ito