<p>[Following a suggestion of Kaveh, I am putting my (somewhat extended) comment as an answer]</p>

<p>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.</p>

<p>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 <em>gradually</em> 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 <em>algorithm</em>, however, does more: it gives <em>one</em> "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>

<p>P.S. Sorry, forgot to add: An excellent confirmation of my "thesis" that circuits should be viewed as (static) <em>codes</em> rather than (dynamic) <em>algorithms</em> 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 <em>encode</em> 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.</p>

CC BY-SA 3.0
2015-07-08T15:42:35.840Z
Are there any non-trivial examples of languages that support this conjecture?
Igor Shinkar
CC BY-SA 3.0
2015-07-08T19:42:01.953Z
@Igor: I don't know. Some (weak) indications are mentioned
[here](https://books.google.de/books?id=rHn7hXxyPAkC&pg=PA564&dq=jukna+boolean+function+complexity+kolmogorov&hl=de&sa=X&ei=kXmdVbbWFYroUq2tgqAL&ved=0CCgQ6AEwAA#v=onepage&q=jukna%20boolean%20function%20complexity%20kolmogorov&f=false). 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
CC BY-SA 3.0
2014-04-10T15:30:43.403Z
2014-05-06T05:36:44.700Z
2014-05-06T05:36:44.700Z
Stasys
<p>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.</p>

<p>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:</p>

<blockquote>
  <p>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 $+$.</p>
</blockquote>

<p>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)$.</p>

<p>Sorry I'm not qualified to be more precise than this -- if anyone else has heard this idea, maybe they could help me out.</p>

CC BY-SA 3.0
2014-05-07T04:36:18.997Z
can you give a ref for that thm plz
vzn
CC BY-SA 3.0
2014-05-14T15:15:23.980Z
@GMB: well observed - this could be even closer explanation for the reason to rise that conjecture.
Stasys
CC BY-SA 3.0
2014-05-07T03:01:00.800Z
2014-05-07T03:01:00.800Z
GMB
<p>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?</p>

CC BY-SA 3.0
2014-04-08T03:12:32.100Z
Paging @Stasys :)
Suresh Venkat
CC BY-SA 3.0
2014-04-08T07:57:08.107Z
refer also this here http://rjlipton.wordpress.com/2009/02/12/is-np-too-big-or-p-too-small/
Turbo
CC BY-SA 3.0
2014-04-08T15:29:06.983Z
SJ also mentions same page that P in linear size circuits implies P≠NP!
vzn
CC BY-SA 3.0
2014-04-08T16:36:34.463Z
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](http://people.cs.uchicago.edu/~fortnow/papers/quaderni.pdf) 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
CC BY-SA 3.0
2014-04-08T18:49:23.663Z
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
CC BY-SA 3.0
2014-04-08T22:24:21.937Z
@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
CC BY-SA 3.0
2014-04-09T06:21:19.613Z
@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
CC BY-SA 3.0
2014-04-22T18:20:00.447Z
@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
CC BY-SA 3.0
2014-04-23T03:18:27.867Z
@JoshuaGrochow Fair point! For some reason I was associating Kannan's theorem more with the win-win analysis.
Sasho Nikolov
CC BY-SA 3.0
2014-05-06T18:56:01.037Z
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?](http://rjlipton.wordpress.com/the-gdel-letter/) (1956)
vzn
CC BY-SA 3.0
2015-12-31T23:23:23.133Z
@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
CC BY-SA 3.0
2016-01-01T04:31:33.990Z
@Turbo because reductions can blow up instance sizes
Sasho Nikolov
CC BY-SA 3.0
2016-01-01T22:11:40.063Z
@SashoNikolov is there a reasonable scenario all reductions could be linear?
Turbo
CC BY-SA 3.0
2016-01-02T12:12:28.687Z
@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
CC BY-SA 3.0
2016-01-02T16:02:43.610Z
@SashoNikolov so assumption SAT having linear size circuit was wrong. Correct (if all reductions are linear)?
Turbo
CC BY-SA 3.0
2016-01-02T23:13:24.010Z
@Turbo I dont see why SAT having linear size circuits implies P = NP.
Sasho Nikolov
CC BY-SA 3.0
2016-01-02T23:19:14.313Z
@SashoNikolov sorry I thought if the smallest boolean circuit that solves 3SAT is n^c size then P=NP
Turbo
<cc.complexity-theory><reference-request><circuit-complexity><ho.history-overview>
Kolmogorov's conjecture that $P$ has linear-size circuits
Hamid
# Kolmogorov's conjecture that $P$ has linear-size circuits

(Asked by: username_0 on 2014-04-08)

In his book, Boolean Function Complexity, username_4 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?

**Tags:** cc.complexity-theory, reference-request, circuit-complexity, ho.history-overview

> **Comments:**
> **username_1**: Paging @username_4 :)  
> **username_2**: refer also this here http://rjlipton.wordpress.com/2009/02/12/is-np-too-big-or-p-too-small/  
> **username_3**: SJ also mentions same page that P in linear size circuits implies P≠NP!  
> **username_3**: 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](http://people.cs.uchicago.edu/~fortnow/papers/quaderni.pdf) 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"  
> **username_4**: 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 ...  
> **username_5**: @username_3 $\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.  
> **username_6**: @username_4, 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).  
> **username_7**: @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).  
> **username_5**: @JoshuaGrochow Fair point! For some reason I was associating Kannan's theorem more with the win-win analysis.  
> **username_3**: 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?](http://rjlipton.wordpress.com/the-gdel-letter/) (1956)  
> **username_2**: @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)?  
> **username_5**: @username_2 because reductions can blow up instance sizes  
> **username_2**: @SashoNikolov is there a reasonable scenario all reductions could be linear?  
> **username_5**: @username_2 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?  
> **username_2**: @SashoNikolov so assumption SAT having linear size circuit was wrong. Correct (if all reductions are linear)?  
> **username_5**: @username_2 I dont see why SAT having linear size circuits implies P = NP.  
> **username_2**: @SashoNikolov sorry I thought if the smallest boolean circuit that solves 3SAT is n^c size then P=NP  

---

## 2 answers

### Answer by username_4 on 2014-04-10. Score: 25

[Following a suggestion of username_6, 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.

> **Comments:**
> **username_8**: Are there any non-trivial examples of languages that support this conjecture?  
> **username_4**: @Igor: I don't know. Some (weak) indications are mentioned [here](https://books.google.de/books?id=rHn7hXxyPAkC&pg=PA564&dq=jukna+boolean+function+complexity+kolmogorov&hl=de&sa=X&ei=kXmdVbbWFYroUq2tgqAL&ved=0CCgQ6AEwAA#v=onepage&q=jukna%20boolean%20function%20complexity%20kolmogorov&f=false). Actually, I tend to the answer of username_9: most probably, the conjecture was stimulated by their solution of the 13th Hilbert's problem, not by combinatorial considerations.  

---

### Answer by username_9 on 2014-05-07. Score: 8

I'm nowhere near as knowledgeable about this topic as username_4, 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.

> **Comments:**
> **username_3**: can you give a ref for that thm plz  
> **username_4**: @username_9: well observed - this could be even closer explanation for the reason to rise that conjecture.  

---

