A conjectura de Kolmogorov de que

Em seu livro Boolean Function Complexity, Stasys Jukna menciona (página 564) que Kolmogorov acreditava que toda linguagem em P possui circuitos de tamanho linear. Nenhuma referência é mencionada e não consegui encontrar nada online. Alguém sabe mais sobre isso?

[Seguindo uma sugestão de Kaveh, estou colocando meu comentário (um tanto estendido) como resposta]

Essa "conjectura" de Kolmogorov é apenas um boato. Não foi publicado em nenhum lugar. Na ex-URSS, "publicar" matemática significava algo diferente do que hoje: dar uma palestra em um seminário ou contar aos colegas na hora do almoço. Contar papéis não era um problema. (Na verdade, eu também ordenei esse modo de fazer matemática.) Não posso excluir a possibilidade de que essa "conjectura" tenha sido contada a Levin por Kolmogorov durante sua caminhada para um seminário na Universidade de Moscou. Portanto, não leve isso tão a sério como uma conjectura formal; é apenas um boato de que (desnecessário dizer) não foi refutado ao longo dos anos. Mas como um gigante como Kolmogorov pensou seriamente sobre esse problema e não excluiu a possibilidade de um "poder do diabo", a conjectura deve ser tratada com seriedade o suficiente,

Aqui está uma especulação (muito, muito grosseira) da minha compreensão dessa conjectura. Nossa intuição (aparentemente errada) sobre como os circuitos funcionam depende da visualização da computação por um programa como um processo seqüencial que gradualmente coleta informações sobre a sequência de entrada. Essa intuição é emprestada de nossa visão de como uma máquina de Turing funciona. Mas cada sequência de entrada determina um subcircuito (testemunhando f ( x ) = 1 ou f ( x ) = 0 ). E para que um circuito esteja correto, basta que os conjuntos de subcircuitos para f - 1 ( 1 ) e$x$$f(x)=1$$f(x)=0$$f^{-1}(1)$ são disjuntos. Ou seja, um circuito é uma "codificação local" compacta de uma determinada partição do n- cubo. O comprimento desse código é a complexidade de Kolmogorov da sequência binária fornecida f n de comprimento 2 n . Umalgoritmo detempo polinomial, no entanto, faz mais: forneceuma"codificação global" de toda a cadeia infinita f para todos os n . Agora, uma sequência infinita f permite uma codificação de tamanho n $f^{-1}(0)$$n$$f_n$$2^n$$f$$n$$f$$n^c$deve ser "simples" e seus prefixos "devem" permitir codificações "locais" ainda mais compactas. Obviamente, permanece um mistério o porquê de Kolmogorov pensar que codificações "locais", mesmo do tamanho para alguns c, podem ser suficientes ...$cn$$c$

PS Desculpe, esqueci de acrescentar: Uma excelente confirmação da minha "tese" de que os circuitos devem ser vistos como códigos (estáticos) e não como algoritmos (dinâmicos) é o famoso teorema de David Barrington de que toda a classe pode ser simulada por polinômios programas de ramificação de tamanho 5. de largura 5. A visão "coleta de informações" aqui está totalmente errada: nem sequer está claro como calcular a função majoritária mantendo apenas 5 bits de informação. Uma ideia inteligente de David era apenas codificar$NC^1$o comportamento de uma dada fórmula por seqüências particulares de 5 permutações e mostrar que seqüências aceitas e rejeitadas receberão códigos diferentes. O ponto é que um programa de ramificação também não "calcula" --- codifica as seqüências de entrada pelos subprogramas: quando uma entrada chega, arestas inconsistentes desaparecem e temos um código dessa entrada.

Não estou tão bem informado sobre esse tópico quanto a Stasys, mas ouvi uma justificativa diferente para essa conjectura que eu também poderia compartilhar.

Ouvi dizer que a conjectura se baseava na solução positiva para o décimo terceiro problema de Hilbert, que foi resolvido em conjunto por Komolgorov e seu aluno Arnold. O teorema (que é muito mais geral do que o problema declarado de Hilbert) diz:

Toda função contínua de um número finito de variáveis ​​pode ser expressa como a composição finita de funções de variável única, bem como um número finito de aplicações do operador binário .$+$

Disseram-me que, com base em alguns detalhes de implementação da prova deste teorema, isto pode ser visto como um análogo contínua da alegação de que .$\exists k \, \, \, P \subset SIZE(n^k)$

Desculpe, não estou qualificado para ser mais preciso do que isso - se alguém já ouviu essa ideia, talvez eles possam me ajudar.