Aplicações da complexidade de Kolmogorov na teoria dos números

Quais são as aplicações da complexidade de Kolmogorov na teoria dos números e em campos relacionados a provas? (A monografia de Li & Vitanyi não possui muitas aplicações relacionadas à Teoria dos Números.)

Uma das boas provas que encontrei é a prova da existência de um número infinito de números primos, usando a definição de Complexidade de Kolmogorov e o fator de compressão.

Além disso, qual é a importância da complexidade de Kolmogorov em criptografia?

reference-request big-list it.information-theory kolmogorov-complexity Subhayan
fonte

Poderia, por favor, apontar-me para a prova baseada na complexidade de Kolmogoroff da infinidade de primos?

Martin Berger

@MartinBerger: veja o livro de Li e Vitanyi ou esta nota de Lance Fortnow

Marzio De Biasi

ok, isso é um pouco estranho, mas não consigo me lembrar de onde me deparei com isso, a prova é algo como isto .. suponha que você escolha um inf. conjunto

tal que

é positivo e

S = n_{1}, n_{2}, . . .

$S = {n_1,n_2,...}$

n

$n$

. Agora,para fins de contradição,suponha que haja apenas um número finito de números primos,

K (n) \geq \frac{l o g_{2} n}{2}

$K(n) \geq \frac{log_2 n}{2}$

\forall n \in S

$\forall n \in S$

p_{1} . . . p_{m}

${p_1...p_m}$

Subhayan

[cont] Assim, podemos agora representar qualquer

como

. Como assumimos que existem apenas finitos (

) primos, eles têm uma representação fixa. Então

depende apenas dos valores de

s .. então, para resumir,

n_{i}

$n_i$

Σ_{j = 1}^{m} p_{j}^{v_{i, j}}

$\Sigma_{j=1}^{m}p_j^{v_{i,j}}$

m

$m$

K (n_{i})

$K(n_i)$

v_{i, j}

$v_{i,j}$

... que pode ser, no máximo, alguns

... mas depois declarou

K (n_{i}) = c o n s t + Σ_{j = 1}^{m} l o g_{2} (v_{i, j} + 1)

$K(n_i) = const + \Sigma_{j=1}^{m}\ log_2(v_{i,j}+1)$

c o n s t + m . l o g_{2} l o g_{2} n_{i}

$const + m.log_2log_2n_{i}$

. Portanto)isto implica que

K (n) \geq \frac{l o g_{2} n}{2}

$K(n) \geq \frac{log_2 n}{2}$

\forall n \in S

$\forall n \in S$

mas isso só é verdade para um número finito de

. Assim chegamos a uma contradição

\frac{l o g_{2} n_{i}}{2} \leq m . l o g_{2} l o g_{2} n_{i}

$\frac{log_2 n_i}{2} \leq m.log_2log_2n_{i}$

n_{i}

$n_i$

Subhayan

Gosto do segundo exemplo do NT das anotações de Lance: que o

ésimo número primo

é no máximo

. Este é um log off do teorema de número primo, ea prova é tão fácil quanto a prova da infinitude dos números primos via K. complexidade

k

$k$

p_{k}

$p_k$

p_{k} \leq k \log^{2} k

$p_k \leq k\log^2 k$

Sasho Nikolov

Respostas:

Todo número inteiro tem uma complexidade Kolmogorov associada; o programa mais curto que imprime esse número inteiro.

Existem primos atépara que os primos tenham menor complexidade Kolmogrov do que os compósitos, em média; $\approx {x \over ln(x)}$ $x$ vs . $\approx ln({x \over ln(x)})$ $\approx ln(x)$

Como efeito colateral, você deve ter grandes lacunas entre os números primos; caso contrário, você pode codificar cada número como o primo anterior mais um pequeno número de bits.

Chad Brewbaker
fonte

Existem grandes lacunas entre os primos por causa do teorema do número primo, não acho que você precise adicionar a complexidade de Kolmogorov na mistura para mostrar isso.

Sasho Nikolov

A teoria dos números geralmente preocupa-se com equações inteiras, embora a Wikipedia observe , de maneira mais ampla, uma sub-ramificação da teoria dos números é a aproximação dos reais pelos racionais e a relação entre eles: "Também é possível estudar números reais em relação aos números racionais, por exemplo, conforme aproximado pelo último ( aproximação diofantina ). "

Aqui estão dois documentos geralmente nesse sentido:

A complexidade de Kolmogorov de números reais Ludwig Staiger
Caracterização de reais aleatórios ce Cristian S. Calude

vzn
fonte

Que parte da complexidade de Komolgorov não pode ser aplicada a equações inteiras? Embora seja verdade que o assunto geralmente se preocupa com o infinito, a teoria dos números também pode (por exemplo, equações diofantinas etc.) e, é claro, existem várias versões do KC limitadas por recursos que podem ser relevantes, etc. Não sei ao certo onde 'A teoria dos números geralmente se preocupa com equações inteiras' tem algo a ver com a existência de aplicações de KC no tópico.

Steven Stadnicki

o ponto é que, em uma pesquisa on-line superficial, ainda não encontrei referências que relacionam KC diretamente à teoria dos números, mas há algumas que relacionam isso à análise de reais e aproximações racionais de uma maneira que se limita à teoria dos números.

vzn

sim, eu também tentei pesquisar sobre as aplicações do KC na teoria dos números, no entanto, não consegui encontrar nada, agora o KC parece ser uma boa maneira de resolver alguns problemas na teoria dos números .. deve haver algumas provas fundamentais (aplicações) aqui ..

Subhayan 05/09

-2

tente esta referência

Do teorema de Kolmogorov sobre distribuição empírica à teoria dos números , Kevin Ford, também aqui .

Descrevemos algumas novas estimativas para a probabilidade de uma função de distribuição empírica permanecer em um lado de uma determinada linha e aplicamos a teoria dos números.

$K(x)$
$K(x)$ $K(x)$ é ao mesmo tempo a medida mais estrita de entropia e, ao mesmo tempo, a mais intratável, com outras medidas de entropia em outros pontos "mais fáceis" nesse aparente contínuo e rígido troco.

vzn
fonte

-1: O teorema de Kolmogorov na primeira referência não está relacionado à complexidade de Kolmogorov. É um resultado famoso sobre a convergência da função de distribuição empírica das amostras do IID para o CDF.

Sasho Nikolov

concordou nesse ponto, oops = (

vzn 4/13/13