Aplicaciones de complejidad de Kolmogorov en complejidad computacional

Hablando informalmente, la complejidad de Kolmogorov de una cadena es la longitud de un programa más corto que genera x . Podemos definir una noción de 'cadena aleatoria' usándola ( x es aleatoria si K ( x ) ≥ 0.99 | x | ) Es fácil ver que la mayoría de las cadenas son aleatorias (no hay tantos programas cortos).$x$$x$$x$$K(x) \geq 0.99 |x|$

La teoría de la complejidad de Kolmogorov y la teoría de la información algorítmica están bastante desarrolladas hoy en día. Y hay varios ejemplos divertidos del uso de la complejidad de Kolmogorov en pruebas de diferentes teoremas que no contienen nada sobre la complejidad de Kolmogorov en sus afirmaciones ( LLL constructiva , desigualdad de Loomis-Whitney, etc.).

¿Hay alguna buena aplicación de la complejidad de Kolmogorov y la teoría de la información algorítmica en la complejidad computacional y campos relacionados ? Creo que debería haber resultados que utilicen la complejidad de Kolmogorov como un reemplazo directo de argumentos de conteo simples. Esto, por supuesto, no es tan interesante.

Lance Fortnow ha escrito un artículo sobre este tema: la complejidad de Kolmogorov y la complejidad computacional

También debe consultar Una introducción a la complejidad de Kolmogorov y sus aplicaciones de Li y Vitanyi, el libro definitivo sobre el tema. En particular, el capítulo 6 "El Método de Incompresibilidad" analiza una serie de aplicaciones en complejidad, como una prueba de complejidad de Kolmogorov del lema de conmutación de Hastad (de Circuit Lower Bounds à la Kolmogorov de Fortnow y Laplante).

Y hay aplicaciones en la complejidad de la comunicación (por ejemplo, la complejidad de Kolmogorov y los métodos combinatorios en la complejidad de la comunicación de Kaplan y Laplante).

Hace solo unos días, Scott Aaronson utilizó un argumento basado en la complejidad de Kolmogorov para mostrar la Equivalencia de muestreo y búsqueda . Además, argumenta que, en su argumento, la complejidad de Kolmogorov se usa de una manera esencial, que no es solo un atajo para un argumento de conteo.

Este resultado de Alon et al. Se puede obtener por medio de la complejidad de Kolmogorov.

"El conjunto de aristas E de cada finita bipartita gráfica se puede dividir en subconjuntos para que todos los grafos bipartitos resultantes son casi normal".$\mathrm{poly}(\log |E|)$

Un excelente documento que conozco (además de los otros excelentes documentos mencionados en otras respuestas):

Juris Hartmanis, Complejidad de Kolmogorov generalizada y la estructura de computaciones factibles , FOCS 1983.

Lo principal que recuerdo de ese artículo es una construcción basada en la complejidad de Kolmogorov de un oráculo que separa P de NP.

Otro artículo que viene a la mente es

Allender et al., Power from Random Strings , FOCS 2002 ( versión ECCC ) y SICOMP 2006 .

Si mal no recuerdo, el último artículo separa la integridad de Turing en tiempo polinomial de la integridad de muchos en el espacio logarítmico en PSPACE, utilizando argumentos de complejidad de Kolmogorov. Por supuesto, hace muchas otras cosas, pero recuerdo que la separación es una aplicación que es de interés independiente fuera de la teoría de la información algorítmica.

También hay una técnica cuántica de límite inferior que utiliza la complejidad de Kolmogorov:

" Límites inferiores para la complejidad de consultas aleatorias y cuánticas utilizando argumentos de Kolmogorov " por Sophie Laplante y Frederic Magniez

$s$$K(s)$

(Ahora, en serio). Daniil Musatov ha demostrado recientemente que la desrandomización ingenua puede proporcionar construcciones razonables para los objetos que generalmente se muestran de manera no constructiva a través del método probabilístico. Creo que es probable que esto proporcione aplicaciones futuras significativas de la complejidad de Kolmogorov limitada a los recursos a la complejidad computacional.

• Daniil Musatov, Mejorando la versión espacial del teorema de la complejidad condicional de Muchnik a través de la desrandomización `` ingenua '' , CSR 2011, LNCS 6651, 64-76. doi: 10.1007 / 978-3-642-20712-9_6 ( preimpresión )

Ver también los documentos que citan este .

(Editar: enlace a la versión posterior publicada).

H. Buhrman, L. Fortnow y S. Laplante. Complejidad de Kolmogorov limitada por recursos revisitada. SIAM Journal on Computing, 31 (3): 887-905, 2002. ( revista , página web de Lance ).

Incluye aplicaciones de complejidad de Kolmogorov como:

• Una prueba de Valiant-Vazirani
• Las asignaciones satisfactorias de fórmulas booleanas se pueden enumerar en un polinomio de tiempo en el tamaño de salida si se puede encontrar rápidamente una asignación única
• Una nueva prueba de que BPP está en Sigma_2 P
• Varias construcciones de oráculo

Algunos de los anteriores se probaron por primera vez en este documento, mientras que otros son simplemente nuevas pruebas de viejos teoremas, utilizando la complejidad de Kolmogorov.

Las aplicaciones de la complejidad de Kolmogorov limitada en el tiempo en la teoría de la complejidad es una buena encuesta realizada por Eric Allender sobre otras aplicaciones. Aunque muchos de los resultados aquí son implicaciones, algunos son aplicaciones verdaderas, como las siguientes:

• Cor 13: En relación con un oráculo genérico, no existe un generador pseudoaleatorio que sea seguro contra los adversarios P ​​/ poly.
• Thm 16 [Allender y Gore, 1991]: hay un oráculo en relación con el cual todos los predicados de NE se pueden resolver en tiempo exponencial y E = Union_k \ Sigma_k-TIME (n).

Ambas pruebas utilizan la complejidad de Kolmogorov significativamente.

$D$$D$

Descripción mínima La longitud utiliza la complejidad de Kolmogorov (o aproximaciones y generalizaciones de la misma, debido a la indecidibilidad) en el aprendizaje teórico de la información y la teoría de la inferencia. Específicamente, MDL se utiliza para encontrar explicaciones de datos que naturalmente evitan el sobreajuste.

Jorma Rissanen ofrece una buena introducción a su concepto: http://www.mdl-research.org/jorma.rissanen/pub/Intro.pdf

¿Te refieres a algo como esto, ilyaraz?

http://arxiv.org/abs/1004.3993