19
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ I wonder: Do we have candidates for refuting Kolmogorov's conjecture? Of course, one may consider any problem that provably has super-linear complexity. Maybe some of them are more likely not to have linear-size circuits? $\endgroup$ – Bruno May 6 '14 at 6:38
  • 2
    $\begingroup$ lets face it, nobody has the slightest clue. (re goldman quote on hollywood: "nobody knows anything.") the (unpublished) conjecture has maybe been open even longer than P=?NP. however, a rough idea/angle worth exploring: compression theory & compressibility. this is basically what williams is alluding to and could possibly be at the heart of many complexity class separations. the idea is that there are basic ways/algorithms to encode data, and some patterns are intrinsically harder to compress using (any arbitrary) encodings. but there seem to be very few results in this area also. $\endgroup$ – vzn May 6 '14 at 16:43
  • 1
    $\begingroup$ and btw, the many connections of Kolmogorov complexity to computational complexity eg explored by Fortnow might have some explanatory connection to why the questions are so hard to resolve, because so many Kolmogorov complexity related questions are undecidable...? $\endgroup$ – vzn May 7 '14 at 4:44
  • 1
    $\begingroup$ @Bruno: I would guess that $\mathsf{P}$-complete problems would be good candidates, e.g. Linear Programming or the Circuit Value Problem. If $\mathsf{P} \not\subseteq \mathsf{NC}$ then these problems can't be solved even nonuniformly in poly-size and poly-logarithmic depth, so it at least seems reasonable to guess that such problems shouldn't be solvable in linear size (and unrestricted depth) either. The determinant might be another reasonable candidate. But these are just proposals - I don't have strong reasons for thinking they have super-linear circuit size. $\endgroup$ – Joshua Grochow Dec 1 '14 at 3:50
22
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ It would be very interesting if the discrete analog that Kolmogorov believed in would indeed exist. Presumably, researchers have tried to find it, since it could lead as far as to a proof of $P\neq NP$. What was the main roadblock they encountered? $\endgroup$ – Andras Farago May 12 '14 at 23:13
  • 3
    $\begingroup$ Roadblocks? I don't think anyone has found the road :) Since most people believe that $P$ doesn't have $O(n^k)$ size circuits, for every fixed $k$, probably few people have even looked for the road. $\endgroup$ – Ryan Williams May 12 '14 at 23:49
11
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.