In his book, Boolean Function Complexity, Stasys Jukna mentions (page 564) that Kolmogorov believed that every language in P has circuits of linear size. No reference is mentioned and I couldn't find anything online. Does anyone know more about this?
-
4$\begingroup$ Paging @Stasys :) $\endgroup$– Suresh VenkatApr 8, 2014 at 3:12
-
7$\begingroup$ refer also this here rjlipton.wordpress.com/2009/02/12/is-np-too-big-or-p-too-small $\endgroup$– TurboApr 8, 2014 at 7:57
-
19$\begingroup$ This "conjecture" of Kolmogorov is just a rumor. It was of course nowhere published or so. In the former USSR, "publishing" mathematics meant something different: do a talk in a seminar, or tell your colleagues at lunch, or else. Counting papers was not an issue. So, I cannot exclude that this "conjecture" was just told to Levin by Kolmogorov during their walk to a seminar in MGU (Moscow University). (Actually, I've also enjoined this way of doing math.) So, don't take this too seriously - just as a "rumor", which (needless to say) hasn't been refuted over the years ... $\endgroup$– StasysApr 8, 2014 at 18:49
-
5$\begingroup$ @vzn $\mathsf{P} \subseteq \mathsf{size}(n^k) \Rightarrow \mathsf{P} \neq \mathsf{NP}$ for any fixed $k$ because $\forall k \in \mathbb{N}: \Sigma_4^{\mathsf{P}} \not \subseteq \mathsf{size}(n^k)$. The latter is strengthened to $\Sigma_2^{\mathsf{P}}$ by Kannan's theorem. $\endgroup$– Sasho NikolovApr 8, 2014 at 22:24
-
2$\begingroup$ @Stasys, you should post that as an answer so the question becomes answered (so the site will not keep bumping it up to the front page). $\endgroup$– KavehApr 9, 2014 at 6:21
2 Answers
[Following a suggestion of Kaveh, I am putting my (somewhat extended) comment as an answer]
This "conjecture" of Kolmogorov is just a rumor. It was not published anywhere. In the former USSR, "publishing" mathematics meant something different than what it does today: give a talk at a seminar or tell your colleagues at lunch. Counting papers was not an issue. (Actually, I've also enjoined this way of doing math.) I cannot exclude the possibility that this "conjecture" was just told to Levin by Kolmogorov during their walk to a seminar at Moscow University. So don't take this too seriously as a formal conjecture; it is just a rumor that (needless to say) hasn't been refuted over the years. But since a giant such as Kolmogorov seriously thought about this problem, and hasn't excluded the possibility of a "devil's power", the conjecture should be treated seriously enough, just as a warning about our possibly wrong intuition on what circuits actually do.
Here is a (very, very rough) speculation of my understanding of this conjecture. Our (apparently wrong) intuition about how circuits work relies on viewing the computation by a program as a sequential process which gradually collects information about the input string. This intuition is borrowed from our view of how a Turing machine works. But each input string $x$ determines a subcircuit (witnessing $f(x)=1$ or $f(x)=0$). And for a circuit to be correct, it is enough that the sets of subcircuits for $f^{-1}(1)$ and $f^{-1}(0)$ are disjoint. That is, a circuit is a compact "local encoding" of a given partition of the $n$-cube. The length of this code is the Kolmogorov complexity of the given binary string $f_n$ of length $2^n$. A polynomial time algorithm, however, does more: it gives one "global encoding" of the entire infinite string $f$ for all $n$. Now, an infinite string $f$ allowing an encoding of size $n^c$ must be "simple", and its prefixes "should" allow even more compact "local" encodings. Of course, it remains a mystery why Kolmogorov thought that "local" encodings even of size $cn$ for some $c$ may then be sufficient...
P.S. Sorry, forgot to add: An excellent confirmation of my "thesis" that circuits should be viewed as (static) codes rather than (dynamic) algorithms is the famous theorem of David Barrington that the entire class $NC^1$ can be simulated by polynomial-size branching programs of width 5. The "gathering information" view here is totally wrong: it is not even clear how to compute the majority function by keeping only 5 bits of information. A clever idea of David was just to encode the behavior of a given formula by particular sequences of 5-permutations, and to show that accepted and rejected strings will get different codes. The point is that a branching program also does not "compute" --- it rather encodes input strings by its sub-programs: when an input arrives, inconsistent edges disappear, and we have a code of this input.
-
$\begingroup$ Are there any non-trivial examples of languages that support this conjecture? $\endgroup$ Jul 8, 2015 at 15:42
-
I'm nowhere near as knowledgeable about this topic as Stasys, but I heard a different justification for this conjecture which I might as well share.
I heard that the conjecture was based on the positive solution to Hilbert's Thirteenth Problem, which was jointly resolved by Komolgorov and his student Arnold. The theorem (which is much more general than Hilbert's stated problem) says:
Every continuous function of a finite number of variables can be expressed as the finite composition of single-variable functions, as well as a finite number of applications of the binary operator $+$.
I'm told that, based on some implementation details of the proof of this theorem, this can be viewed as a continuous analogue of the claim that $\exists k \, \, \, P \subset SIZE(n^k)$.
Sorry I'm not qualified to be more precise than this -- if anyone else has heard this idea, maybe they could help me out.
-
-
$\begingroup$ @GMB: well observed - this could be even closer explanation for the reason to rise that conjecture. $\endgroup$– StasysMay 14, 2014 at 15:15