28

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?

Hermann Gruber
  • 6,470
  • 1
  • 35
  • 58
Hamid
  • 381
  • 2
  • 4
  • 4
    Paging @Stasys :) – Suresh Venkat Apr 08 '14 at 03:12
  • 7
    refer also this here http://rjlipton.wordpress.com/2009/02/12/is-np-too-big-or-p-too-small/ – Turbo Apr 08 '14 at 07:57
  • SJ also mentions same page that P in linear size circuits implies P≠NP! – vzn Apr 08 '14 at 15:29
  • RJLipton quotes Levin as stating the conjecture & attributing it to Kolmogorov, Kolmogorov was his advisor. there seems to be connections to Kolmogorov/computational complexity as surveyed by Fortnow with many thms but it would be difficult to isolate which thm in the paper most closely relates although sec 8 seems to come close, "Kolmogorov characterization of complexity classes" – vzn Apr 08 '14 at 16:36
  • 19
    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 ... – Stasys Apr 08 '14 at 18:49
  • 5
    @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. – Sasho Nikolov Apr 08 '14 at 22:24
  • 2
    @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). – Kaveh Apr 09 '14 at 06:21
  • 1
    @Sasho: This is neither here nor there, but the result that $\mathsf{\Sigma_4 P} \not\subseteq \mathsf{SIZE}(n^k)$ is really the heart of Kannan's Theorem. The latter then gets strengthened to $\mathsf{\Sigma_2 P}$ using Karp-Lipton(-Sipser). – Joshua Grochow Apr 22 '14 at 18:20
  • @JoshuaGrochow Fair point! For some reason I was associating Kannan's theorem more with the win-win analysis. – Sasho Nikolov Apr 23 '14 at 03:18
  • another major angle on this? its apparently impossible to date so far. could this have been a historically significant early conjecture? afaik Kolmogorov worked on circuit complexity very early on & this conjecture implies P≠NP. maybe a significant historical element/conjecture around the origins/foundations of complexity theory nearly on par with Godels lost letter? (1956) – vzn May 06 '14 at 18:56
  • @SashoNikolov Since P has linear sized circuits proves P is not NP why doesn't it show 3SAT does not have linear sized circuits (after all every problem in P has a reduction to 3SAT which if it has linear sized circuits then P will have too)? – Turbo Dec 31 '15 at 23:23
  • 1
    @Turbo because reductions can blow up instance sizes – Sasho Nikolov Jan 01 '16 at 04:31
  • @SashoNikolov is there a reasonable scenario all reductions could be linear? – Turbo Jan 01 '16 at 22:11
  • @Turbo actually I dont get your argument at all. Say you could show that a linear size circuit for 3SAT implies P has linear size circuits, which implies P is not equal to NP. Then what? – Sasho Nikolov Jan 02 '16 at 12:12
  • @SashoNikolov so assumption SAT having linear size circuit was wrong. Correct (if all reductions are linear)? – Turbo Jan 02 '16 at 16:02
  • @Turbo I dont see why SAT having linear size circuits implies P = NP. – Sasho Nikolov Jan 02 '16 at 23:13
  • @SashoNikolov sorry I thought if the smallest boolean circuit that solves 3SAT is n^c size then P=NP – Turbo Jan 02 '16 at 23:19

2 Answers2

25

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

argentpepper
  • 2,281
  • 15
  • 27
Stasys
  • 6,765
  • 29
  • 54
  • Are there any non-trivial examples of languages that support this conjecture? – Igor Shinkar Jul 08 '15 at 15:42
  • @Igor: I don't know. Some (weak) indications are mentioned here. Actually, I tend to the answer of GMB: most probably, the conjecture was stimulated by their solution of the 13th Hilbert's problem, not by combinatorial considerations. – Stasys Jul 08 '15 at 19:42
8

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.

GMB
  • 2,393
  • 15
  • 20