Argumentos a favor / contra a conjectura de Kolmogorov sobre a complexidade do circuito de P

De acordo com o relato histórico (não verificado), Kolmogorov pensou que todo idioma em tem complexidade de circuito linear. (Veja a conjectura da pergunta anterior de Kolmogorov de que possui circuitos de tamanho linear .) Observe que isso implica .$\mathsf{P}$$P$$\mathsf{P}\neq \mathsf{NP}$

A conjectura de Kolmogorov, no entanto, parece falhar. Por exemplo, Ryan Williams escreve em um artigo recente : "A conjectura seria surpreendente, se verdadeira. Para idiomas em requerem tempo, parece improvável que a complexidade de tais problemas encolheria magicamente para o tamanho , apenas porque um circuito diferente pode ser projetado para cada comprimento de entrada ".$\mathsf{P}$$n^{100^{100}}$$O(n)$

Por outro lado, Andrey Kolmogorov (1903-1987) é amplamente reconhecido como um dos principais matemáticos do século XX. É bastante difícil imaginar que ele teria proposto uma conjectura completamente absurda. Portanto, para entendê-lo melhor, tentei encontrar alguns argumentos que poderiam realmente apoiar seu palpite surpreendente. Aqui está o que eu poderia pensar:

Suponha . Então, podemos escolher uma linguagem L \ in \ mathsf {P} , de modo que L tenha complexidade superlinear, tanto no modelo uniforme quanto no não uniforme. Existem então duas possibilidades:$\mathsf{P}\not\subseteq \mathsf{SIZE}(lin)$$L\in \mathsf{P}$$L$

1. Há um conhecido explícita algoritmo (máquina de Turing) que aceita $L$ . A partir disso, podemos construir uma família de funções explícita que deve ter complexidade de circuito superlinear. No entanto, isso pode parecer improvável, uma vez que ninguém conseguiu encontrar esse exemplo em mais de 60 anos de intensa pesquisa em circuitos.

2. Não há como conhecido explícita algoritmo para $L$ . Por exemplo, sua existência é comprovada por meios não construtivos, como o Axioma da Escolha. Ou, mesmo que o algoritmo explícito exista, ninguém foi capaz de encontrá-lo. Dado, no entanto, que existem infinitas línguas que podem desempenhar o papel de $L$ , é improvável novamente que todas elas se comportem dessa maneira hostil.

Porém, se rejeitarmos ambas as opções como improváveis, a única possibilidade restante é que esse $L$ não exista. Isso significa $\mathsf{P}\subseteq \mathsf{SIZE}(lin)$ , que é precisamente a conjectura de Kolmogorov.

Pergunta: Você pode pensar em outro argumento a favor / contra a conjectura de Kolmogorov?

A nota de rodapé do meu artigo que você cita refere-se a um "argumento" heurístico, bem como, pelo menos, o que pensamos ser a intuição de Kolmogorov - a resolução positiva do décimo terceiro problema de Hilbert.

http://en.wikipedia.org/wiki/Hilbert's_thirteenth_problem

Em particular, foi provado por Kolmogorov e Arnold que qualquer função contínua em variáveis ​​pode ser expressa como uma composição de funções "simples": adição de duas variáveis ​​e funções contínuas em uma variável. Portanto, na "base" de funções contínuas de uma variável e adição de duas variáveis, toda função contínua em variáveis ​​tem "complexidade de circuito" .$n$$O(n^2)$$n$$O(n^2)$

Parece que Kolmogorov acreditava que existe um analógico discreto, em que "contínua em variáveis" se torna "Booleana em variáveis ​​e tempo poli computável", e onde a "base" dada acima se torna funções booleanas de duas variáveis.$n$$n$$(n)$

$t$$t$$\mathsf{P}$

$\mathsf{P}$

$j$$1$$j$$0$$j$$j$$n$$2^n$

Nenhuma das opções acima explica por que e" linear "podem ser os respectivos parâmetros corretos para a instrução; mas acho que eles mostram que uma intuição natural - que os circuitos agem como algoritmos, e algoritmos mais complicados exigem circuitos igualmente complicados - podem ser enganosos.$``\mathsf{P}"$