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