Conjetura de Kolmogorov de que

En su libro, Boolean Function Complexity, Stasys Jukna menciona (página 564) que Kolmogorov creía que cada lenguaje en P tiene circuitos de tamaño lineal. No se menciona ninguna referencia y no pude encontrar nada en línea. ¿Alguien sabe más sobre esto?

[Siguiendo una sugerencia de Kaveh, pongo mi comentario (algo extendido) como respuesta]

Esta "conjetura" de Kolmogorov es solo un rumor. No fue publicado en ningún lado. En la antigua URSS, "publicar" las matemáticas significaba algo diferente de lo que hace hoy: dar una charla en un seminario o decirles a sus colegas durante el almuerzo. Contar papeles no era un problema. (En realidad, también he ordenado esta forma de hacer matemáticas.) No puedo excluir la posibilidad de que Kolmogorov le haya dicho esta "conjetura" a Levin durante su caminata a un seminario en la Universidad de Moscú. Así que no te lo tomes tan en serio como una conjetura formal; Es solo un rumor de que (no hace falta decirlo) no ha sido refutado a lo largo de los años. Pero dado que un gigante como Kolmogorov pensó seriamente en este problema, y ​​no ha excluido la posibilidad de un "poder del diablo", la conjetura debe tratarse con la suficiente seriedad,

Aquí hay una especulación (muy, muy aproximada) de mi comprensión de esta conjetura. Nuestra intuición (aparentemente errónea) sobre cómo funcionan los circuitos se basa en ver el cálculo de un programa como un proceso secuencial que gradualmente recopila información sobre la cadena de entrada. Esta intuición está tomada de nuestra visión de cómo funciona una máquina de Turing. Pero cada cadena de entrada determina un subcircuito (testigo de o ). Y para que un circuito sea correcto, es suficiente que los conjuntos de subcircuitos para y sean disjuntos. Es decir, un circuito es una "codificación local" compacta de una partición dada de laf ( x ) = 1 f ( x ) = 0 f - 1 ( 1 ) f - 1 ( 0 ) n f n 2 n f n f n c c n $x$$f(x)=1$$f(x)=0$$f^{-1}(1)$$f^{-1}(0)$$n$-cubo. La longitud de este código es la complejidad de Kolmogorov de la cadena binaria dada de longitud . Sin embargo, un algoritmo de tiempo polinómico hace más: proporciona una "codificación global" de toda la cadena infinita para todo . Ahora, una cadena infinita permite una codificación de tamaño debe ser "simple", y sus prefijos "deberían" permitir codificaciones aún más compactas "locales". Por supuesto, sigue siendo un misterio por qué Kolmogorov pensó que las codificaciones "locales" incluso de tamaño para algunos podrían ser suficientes ...$f_n$$2^n$$f$$n$$f$$n^c$$cn$$c$

PD Perdón, olvidé agregar: Una excelente confirmación de mi "tesis" de que los circuitos deben ser vistos como códigos (estáticos) en lugar de algoritmos (dinámicos) es el famoso teorema de David Barrington de que toda la clase puede ser simulada por polinomio programas de ramificación de gran tamaño de ancho 5. La vista de "recopilación de información" aquí es totalmente errónea: ni siquiera está claro cómo calcular la función mayoritaria manteniendo solo 5 bits de información. Una idea inteligente de David era solo codificar$NC^1$el comportamiento de una fórmula dada por secuencias particulares de permutaciones de 5, y para mostrar que las cadenas aceptadas y rechazadas obtendrán diferentes códigos. El punto es que un programa de ramificación tampoco "computa", sino que codifica cadenas de entrada por sus subprogramas: cuando llega una entrada, desaparecen los bordes inconsistentes, y tenemos un código de esta entrada.

No estoy tan bien informado sobre este tema como Stasys, pero escuché una justificación diferente para esta conjetura que también podría compartir.

Escuché que la conjetura se basaba en la solución positiva al Decimotercer problema de Hilbert, que fue resuelto conjuntamente por Komolgorov y su alumno Arnold. El teorema (que es mucho más general que el problema declarado de Hilbert) dice:

Cada función continua de un número finito de variables puede expresarse como la composición finita de funciones de una sola variable, así como un número finito de aplicaciones del operador binario .$+$

Me dicen que, en base a algunos detalles de implementación de la prueba de este teorema, esto puede verse como un análogo continuo de la afirmación de que .$\exists k \, \, \, P \subset SIZE(n^k)$

Lo siento, no estoy calificado para ser más preciso que esto; si alguien más ha escuchado esta idea, tal vez podrían ayudarme.