O que é uma estimativa da complexidade de Kolmogorov para os primeiros N números inteiros?

9

Estou ciente de que alguns ints têm maior ou menor complexidade de Kolmogorov. Por exemplo, o número 5.41126806512tem uma complexidade muito baixa, como pode ser expresso por 17/pi. Também estou ciente de que, embora o KC varie dependendo da linguagem da expressão, é sempre o mesmo até uma determinada constante. Então, pergunto: existe uma maneira de calcular uma aproximação do KC para os primeiros N ints?

complexity-theory kolmogorov-complexity Viclib
fonte

algoritmos de compressão são tomados como aproximações aproximadas da complexidade de Kolmogorov. O KC, conforme estritamente definido, usa TMs e outros idiomas, está dentro de um fator constante de uma TM. as primeiras N ints podem ser enumeradas por uma TM de tamanho constante.

vzn

11

Você está procurando a complexidade Kolmogorov da sequência ou a sequência das complexidades Kolmogorov ?

1, \dots, N

$1, \dots, N$

K (1), \dots, K (N)

$K(1), \dots, K(N)$

precisa saber é o seguinte

7

Não, não existe um algoritmo geral para calcular uma aproximação aproximada da complexidade de Kolmogorov da sequência . Qualquer algoritmo candidato que você criar terá algumas entradas nas quais ele fornecerá uma resposta ruim (uma fraca aproximação à resposta correta). $1,2,\dots,n$

Denote por a codificação binária do número natural e deixe denotar uma codificação separada por vírgula da sequência . Não é difícil verificar se . Como computar é indecidível, segue-se que calcular uma boa aproximação a também é indecidível. $[n]$ $n$ $[[n]] = [1],[2],\ldots,[n]$ $1,\ldots,n$ $|K([n]) - K([[n]])| = O(1)$ $K([n])$ $K([[n]])$

Além disso, sabe-se que para "a maioria" de números inteiros , . Portanto, para "a maioria" de números inteiros , . $n$ $K([n]) = \Theta(\log n)$ $n$ $K([[n]]) = \Theta(\log n)$

Yuval Filmus
fonte

Isso pressupõe que a pergunta esteja procurando por , mas acho que a leitura interessante da pergunta - como mencionada no comentário de David - é pedir estimativas assintóticas de . em função de .

K ([[n]])

$K([[n]])$

\sum_{i = 1}^{n} K (i)

$\sum_{i=1}^nK(i)$

n

$n$

Steven Stadnicki

2

Uma maneira de expressar a afirmação 'quase todos os números são maximamente aleatórios' é como a afirmação de que . Por conveniência, defina e considere apenas a parte da soma de a ; então, para cada , temos que o número de números desse tamanho com complexidade é (consulte http://en.wikipedia.org/wiki/Kolmogorov_complexity para alguns detalhes disso), para que possamos dividir a soma pela soma dos números ' incompressible' e dos números compressíveis, com o primeiro contribuindo pelo menos $\sum_{i=1}^N K(i) \in\Theta(N\lg N)$ $N=2^k$ $2^{k-1}$ $2^k$ $c$ $\geq k-c$ $2^{k-1}-2^{k-c}$ $c$ $(1-2^{1-c})2^{k-1}(k-c)$ para a soma. Um pouco mais de massagem deve ser suficiente para obter uma constante da forma na frente (ou seja, uma soma de ). $1-o(1)$ $N\lg N-o(N\lg N)$

Steven Stadnicki
fonte

O que é uma estimativa da complexidade de Kolmogorov para os primeiros N números inteiros?

Respostas: