Arguments for/against Kolmogorov's conjecture about the circuit complexity of P

Question

According to (unverified) historical account, Kolmogorov thought that every language in $\mathsf{P}$ has linear circuit complexity. (See the earlier question Kolmogorov'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:

1. 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.

2. 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?

Answer 1

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.

Answer 2

The answer of Stasys on the previous question provides some intuition potentially in favor: https://cstheory.stackexchange.com/a/22048/8243 . I'll try to restate here as I understand it. The key intuition is to view a circuit as, not an algorithm, but an encoding of a set (the set it accepts). We can get an upper-bound on encoding size by algorithm running time (that is, translate a time-$t$ TM into a size-$t$ circuit), but it's not clear what converse relationship should exist. If a language is in $\mathsf{P}$, then perhaps this implies that membership is "local" enough to be encoded very concisely.

That is, membership in $\mathsf{P}$ is a statement about running time of an algorithm whereas linear circuits is (perhaps) a statement about encoding size of sets of fixed-length words. Both are statements about simplicity of the language but they live in maybe quite different worlds.

Another intuition Stasys mentions comes from the "indicator string" of a language, which let's formalize as the infinite string where bit $j$ is $1$ if the $j$th lexicographic string is in the language and is $0$ otherwise. A (polytime) TM for the language is a (fast) oracle for the string --- given $j$ in binary, produce the $j$th bit. A (linear-sized) circuit for inputs of length $n$ is a (concise) oracle for the length-$2^n$ prefix of the string. The conjecture becomes "any infinite string that has a 'fast' oracle has 'concise' prefix-oracles."

None of the above explains why $``\mathsf{P}"$ and "linear" might be the right respective parameters for the statement; but I think they show that one natural intuition -- that circuits act like algorithms, and more complicated algorithms require similarly-complicated circuits -- might be misleading.