Arguments for/against Kolmogorov's conjecture about the circuit complexity of P According to (unverified) historical account, Kolmogorov thought that every language in $\mathsf{P}$ has linear circuit complexity. (See the earlier question Kolmogorov&#39;s conjecture that $P$ has linear-size circuits.) Note that it implies $\mathsf{P}\neq \mathsf{NP}$.

Kolmogorov's  conjecture, however, is viewed likely to fail. For example, Ryan Williams writes in a recent paper: "The conjecture would be surprising, if true. For languages in $\mathsf{P}$ requiring $n^{100^{100}}$
time, it appears unlikely that the complexity of such problems would magically
shrink to $O(n)$ size, merely because a different circuit can be designed for each
input length."

On the other hand, Andrey Kolmogorov (1903-1987) is widely recognized as one of the leading mathematicians of the 20th century. It is rather hard to imagine that he would have proposed a completely absurd conjecture. Therefore, to understand it better, I tried to find some arguments that might actually support his surprising guess. Here is what I could think up:

Assume $\mathsf{P}\not\subseteq \mathsf{SIZE}(lin)$. Then we can pick a language $L\in \mathsf{P}$, such that $L$ has superlinear complexity both in the uniform and in the non-uniform model. There are then two possibilities:


There is a known  explicit algorithm (Turing machine) that accepts $L$. From this we can construct an explicit function family that must have superlinear circuit complexity. However, this may be viewed  unlikely, since no one has been able to find such an example in more than 60 years of intense research on circuits.
There is no known explicit algorithm for $L$. For example, its existence is proved via non-constructive means, such as the Axiom of Choice. Or, even if the explicit algorithm exists, no one has been able to find it. Given, however, that there are infinitely many languages that can play the role of $L$, it is unlikely again that they all behave in this unfriendly way. 


But then, if we dismiss both options as unlikely, the only remaining possibility is that such an $L$ does not exist. That means  $\mathsf{P}\subseteq \mathsf{SIZE}(lin)$, which is precisely Kolmogorov's conjecture. 


  Question: Can you think of any further argument for/against Kolmogorov's conjecture?
The footnote of my paper that you cite refers to a heuristic "argument" as well, at least, what we think was Kolmogorov's intuition -- the positive resolution of Hilbert's thirteenth problem. 

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

In particular, it was proved by Kolmogorov and Arnold that any continuous function on $n$ variables can be expressed as a composition of $O(n^2)$ "simple" functions: addition of two variables, and continuous functions on one variable. Hence, over the "basis" of one-variable continuous functions and two-variable addition, every continuous function on $n$ variables has "circuit complexity" $O(n^2)$.

It seems Kolmogorov believed there is a discrete analog, where "continuous in $n$ variables" becomes "Boolean in $n$ variables and poly$(n)$-time computable", and where the "basis" given above becomes two-variable Boolean functions.