Aplicaciones de la complejidad de Kolmogorov en teoría de números

¿Cuáles son las aplicaciones de la complejidad de Kolmogorov en la teoría de números y en los campos relacionados con las pruebas? (La monografía de Li & Vitanyi no tiene muchas aplicaciones relacionadas con la teoría de números).

Una de las buenas pruebas que he encontrado es la prueba de la existencia de un número infinito de primos, utilizando la definición de la complejidad de Kolmogorov y el factor de compresión.

Además, ¿cuál es la importancia de la complejidad de Kolmogorov en la criptografía?

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

¿Podría por favor señalarme la prueba basada en la complejidad de Kolmogoroff de la infinitud de números primos?

Martin Berger

@MartinBerger: vea el libro de Li y Vitanyi, o esta nota de Lance Fortnow

Marzio De Biasi

Está bien, esto es un poco incómodo, pero parece que no puedo recordar dónde lo encontré, la prueba es algo así ... supongo que eliges un inf. conjunto de tal manera que es positivo y , . Ahora, para fines de contradicción, suponga que solo hay un número finito de primos, .

S = {norte}_{1}, {norte}_{2}, . . .

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

n

$n$

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.] Entonces ahora podemos representar cualquier

como

. Como asumimos que solo hay muchosprimos(

), tienen una representación fija. Entonces

solo depende de

s .. así que 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 puede ser a lo sumo algunas

... pero luego declaramos

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}$

. Por lo tanto)esto 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$

pero esto es cierto solo para un número finito de

. Por lo tanto, llegamos a una contradicción

\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

Me gusta el segundo ejemplo de NT de las notas de Lance: que el

-ésimo número primo

es como máximo

. Este es un cierre de sesión del teorema de los números primos, y la prueba es tan fácil como la prueba de la infinitud de números primos a través de la complejidad K.

k

$k$

p_{k}

$p_k$

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

$p_k \leq k\log^2 k$

Sasho Nikolov

Respuestas:

Cada entero tiene una complejidad de Kolmogorov asociada; El programa más corto que imprime ese número entero.

Hay imprima hastapor lo que los primos tienen una complejidad de Kolmogrov menor que los compuestos en promedio; $\approx {x \over ln(x)}$ $x$ vs . $\approx ln({x \over ln(x)})$ $\approx ln(x)$

Como efecto secundario, debe tener algunos espacios grandes entre los números primos; de lo contrario, podría codificar cada número como el primo anterior más un pequeño número de bits.

Chad Brewbaker
fuente

Hay grandes diferencias entre los números primos debido al teorema de los números primos, no creo que sea necesario agregar la complejidad de Kolmogorov en la mezcla para demostrarlo.

Sasho Nikolov

La teoría de números generalmente se refiere a las ecuaciones de enteros, aunque tenga en cuenta que la wikipedia dice , más ampliamente, una subramificación de la teoría de números es la aproximación de los reales por racionales y la relación entre ellos: "También se pueden estudiar números reales en relación con números racionales, por ejemplo, como aproximado por este último ( aproximación diofantina ) ".

Aquí hay dos documentos generalmente en esa línea:

La complejidad de Kolmogorov de los números reales Ludwig Staiger
Una caracterización de ce reales aleatorios Cristian S. Calude

vzn
fuente

¿Qué parte de la complejidad de Komolgorov no puede aplicarse a las ecuaciones enteras? Si bien es cierto que el tema a menudo se preocupa por el infinito, la teoría de números también puede (por ejemplo, ecuaciones diofantinas, etc.) y, por supuesto, hay varias versiones de KC limitadas por recursos que pueden ser relevantes, etc. No estoy seguro de dónde 'La teoría de números generalmente se refiere a ecuaciones enteras' tiene algo que ver con si hay aplicaciones de KC en el tema.

Steven Stadnicki

el punto es que en una búsqueda en línea superficial no encontré [todavía?] referencias que relacionen directamente KC con la teoría de números, pero hay algunas que lo relacionan con el análisis de aproximaciones reales y racionales de una manera que raya en la teoría de números.

vzn

Sí, yo también traté de buscar aplicaciones de KC en la teoría de números, sin embargo, no pude encontrar nada, ahora KC parece ser una buena manera de abordar algunos problemas en la teoría de números. Debería haber algunas pruebas fundamentales (aplicaciones) aquí ..

Subhayan

-2

prueba esta referencia

Desde el teorema de Kolmogorov sobre distribución empírica hasta la teoría de números , Kevin Ford, también aquí .

Describimos algunas estimaciones nuevas para la probabilidad de que una función de distribución empírica permanezca en un lado de una línea dada, y damos aplicaciones a la teoría de números.

$K(x)$
$K(x)$ $K(x)$ es, al mismo tiempo, la medida más estricta de entropía y, al mismo tiempo, la más intratable, con otras medidas de entropía en otros puntos "más fáciles" en este continuo equilibrio entre estricto y manejable.

vzn
fuente

-1: El teorema de Kolmogorov en la primera referencia no está relacionado con la complejidad de Kolmogorov. Es un resultado famoso sobre la convergencia de la función de distribución empírica de muestras IID al CDF.

Sasho Nikolov

acordado en ese punto, oops = (

vzn