Valores esperados da complexidade de Kolmogorov em uma amostra aleatória

9

A complexidade de Kolmogorov de uma string não é computável. No entanto, em um subconjunto aleatório do tamanho de cadeias binárias de comprimento , quantas são esperadas para ter complexidade menor que algum número inteiro menor que (como uma função de M , n e n_ {0} )?nMnn0nMnn0

vs
fonte
Você está usando a complexidade "padrão" de Kolmogorov aqui ou a complexidade do prefixo?
Aubrey da Cunha
Na verdade, eu estava pensando apenas na complexidade de Kolmogorov. Eu estava adivinhando o limite 2no que o domotorp mencionou quando consideramos o universo de todas as strings. Não estava claro se qualquer resultado 'consistente' para um subconjunto aleatório arbitrário do tamanho M pode ser produzido. No entanto, a complexidade do prefixo nos levaria a um ponto de vista diferente?
vs
Certamente não mudaria a ordem de magnitude, na verdade, acho que agora minha resposta é um limite para as duas versões.
Domotorp 31/08/11
11
Para cada e todo , a probabilidade de uma seqüência aleatória de bits ter a complexidade Kolmogorov é maior que (com ) . Portanto, em uma distribuição aleatória de strings, você deve esperar strings com ... intuitivamente, há uma probabilidade muito alta de escolher uma string com alta complexidade Kolmogorov. c n x K ( x ) n - c 1 - 1ncnxK(x)n-c c=n-n0MM1 1-1 12cc=n-n0 0M K(x)<n0M2(n-n0 0)K(x)<n0 0
Marzio De Biasi

Respostas:

10

A complexidade de Kolmogorov é determinada apenas até alguma constante aditiva, portanto, não é possível fornecer uma resposta exata. O limite que descrevo aqui é ainda mais fraco.

É claro que o número esperado pode ser calculado facilmente, uma vez que sabemos quantas das seqüências têm complexidade menor que , então deixe-me responder isso. Geralmente, é a primeira declaração sobre a complexidade de Kolmogorov que esse número é no máximo - já que existem apenas essas muitas cadeias de comprimento menor. Por outro lado, se o seu programa diz "de comprimento , tomar o th número", então você obtém cordas de complexidade menos de , onde é o versão sem prefixo da complexidade Kolmogorov de (portanto, no máximon 0 2 n 0 - 1 n x 2 n 0 - K ( n ) - C n 0 K ( n ) n log n + log n + O ( 1 ) p x n x n O ( 1 ) p x2nn02n01nx2n0K(n)Cn0K(n)nlogn+logn+O(1)) Em mais detalhe, a cadeia contém em primeiro lugar uma descrição da máquina de Turing que feita de entrada , onde p é a descrição de um programa livre de prefixo que saídas , emite o th número de comprimento , que é os bits e, em seguida, isso é seguido por .pxnxnO(1)px

Provavelmente é possível melhorar esses limites, mas duvido que você possa obter uma resposta exata.

domotorp
fonte
Você poderia explicar um pouco sobre a frase 'se o seu programa disser "de comprimento n, pegue o décimo número" "?
vs
Você está certo, deve ser livre de prefixo lá, eu o corrigi.
domotorp
3

Uma resposta precisa pode ser dada. O número de cadeias de comprimento com complexidade (simples) no máximo é , até um fator constante. Portanto, qualquer processo que escolha aleatoriamente um subconjunto terá, com probabilidade razoável, uma fração de de seqüências de complexidade menores que . Para mostrar nossa afirmação, basta mostrar que o número de strings com complexidade igual a também é dado por . Podemos mostrar o resultado necessário determinando a soma desse valor em de 1 an 0 2 n 0 - K ( n 0 | n ) 2 - K ( n 0 | n ) + O ( 1 ) n 0 k 2 k - K ( k | n ) k n 0 C ( a , b ) = K ( a | C ( a , b ) )nn02n0K(n0|n)2K(n0|n)+O(1)n0k2kK(k|n)kn0. Para mostrar isso, usamos um resultado de aditividade para complexidade simples (devido a B. Bauwens e A. Shen. Um teorema de aditividade para complexidade simples de Kolmogorov . Theory of Computing Systems, 52 (2): 297-302, fev 2013), Aqui indica a complexidade de Kolmogorov sem prefixo. Escolhendo , observa-se que para cada cadeia de bits de complexidade temos Portanto, para cada um desses , temos . SejaK ( ) a = n n b k k = C ( b ) = C ( n , b ) + O ( 1 ) = K ( n | k ) + C ( b | n

C(a,b)=K(a|C(a,b))+C(b|a,C(a,b))+O(1).
K()a=nnbkb C ( b | n , k ) = k - K ( n | k ) + O ( 1 ) k = k - K ( n | k ) O ( 2 k ) b 2 k n C ( b | n , k
k=C(b)=C(n,b)+O(1)=K(n|k)+C(b|n,k)+O(1).
bC(b|n,k)=kK(n|k)+O(1)k=kK(n|k). Agora, pode-se observar que existem no máximo tais cadeias , e cada uma das primeiras lexicograficamente primeiras de comprimento satisfazem . Assim, deles satisfaz .O(2k)b2knC(b|n,k)k+O(1)Ω(2k)C(b|n,k)=k+O(1)
Bruno Bauwens
fonte