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

<p><a href="http://en.wikipedia.org/wiki/Hilbert%27s_thirteenth_problem">http://en.wikipedia.org/wiki/Hilbert's_thirteenth_problem</a></p>

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

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

CC BY-SA 3.0
2014-05-12T23:13:47.530Z
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?
Andras Farago
CC BY-SA 3.0
2014-05-12T23:49:09.373Z
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.
Ryan Williams
CC BY-SA 3.0
2014-05-12T01:54:16.603Z
2014-05-12T01:54:16.603Z
Ryan Williams
<p>The answer of Stasys on the previous question provides some intuition potentially in favor: <a href="https://cstheory.stackexchange.com/a/22048/8243">https://cstheory.stackexchange.com/a/22048/8243</a> . I'll try to restate here as I understand it. The key intuition is to view a circuit as, <strong>not an algorithm, but an encoding</strong> 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.</p>

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

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

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

CC BY-SA 3.0
2014-05-07T21:56:49.657Z
2014-05-07T21:56:49.657Z
2017-04-13T12:32:28.080Z
usul
<p>According to (unverified) historical account, Kolmogorov thought that every language in $\mathsf{P}$ has linear circuit complexity. (See the earlier question <a href="https://cstheory.stackexchange.com/questions/21995/kolmogorovs-conjecture-that-p-has-linear-size-circuits">Kolmogorov&#39;s conjecture that $P$ has linear-size circuits</a>.) Note that it implies $\mathsf{P}\neq \mathsf{NP}$.</p>

<p>Kolmogorov's  conjecture, however, is viewed likely to fail. For example, Ryan Williams writes in a recent <a href="http://www.stanford.edu/~rrwill/ICM-survey.pdf" rel="nofollow noreferrer">paper:</a> "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."</p>

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

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

<ol>
<li><p>There is a known  <em>explicit</em> algorithm (Turing machine) that accepts $L$. From this we can construct an <em>explicit</em> 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.</p></li>
<li><p>There is no known <em>explicit</em> 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 <em>all</em> behave in this unfriendly way. </p></li>
</ol>

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

<blockquote>
  <p><strong>Question:</strong> Can you think of any further argument for/against Kolmogorov's conjecture?</p>
</blockquote>

CC BY-SA 3.0
2014-05-06T06:38:45.093Z
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?
Bruno
CC BY-SA 3.0
2014-05-06T16:43:01.157Z
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.
vzn
CC BY-SA 3.0
2014-05-07T04:44:29.327Z
and btw, the many connections of Kolmogorov complexity to computational complexity eg explored by [Fortnow](http://www.cs.uchicago.edu/~fortnow/papers/quaderni.pdf) might have some explanatory connection to why the questions are so hard to resolve, because so many Kolmogorov complexity related questions are undecidable...?
vzn
CC BY-SA 3.0
2014-12-01T03:50:57.233Z
@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.
Joshua Grochow
<cc.complexity-theory><circuit-complexity><ho.history-overview>
Arguments for/against Kolmogorov's conjecture about the circuit complexity of P
Andras Farago
# Arguments for/against Kolmogorov's conjecture about the circuit complexity of P

(Asked by: username_0 on 2014-05-06)

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](https://cstheory.stackexchange.com/questions/21995/kolmogorovs-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, username_4 writes in a recent [paper:](http://www.stanford.edu/~rrwill/ICM-survey.pdf) "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?

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

> **Comments:**
> **username_1**: 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?  
> **username_2**: 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.  
> **username_2**: and btw, the many connections of Kolmogorov complexity to computational complexity eg explored by [Fortnow](http://www.cs.uchicago.edu/~fortnow/papers/quaderni.pdf) might have some explanatory connection to why the questions are so hard to resolve, because so many Kolmogorov complexity related questions are undecidable...?  
> **username_3**: @username_1: 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.  

---

## 2 answers

### Answer by username_4 on 2014-05-12. Score: 23

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](http://en.wikipedia.org/wiki/Hilbert%27s_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.

> **Comments:**
> **username_0**: 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?  
> **username_4**: 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.  

---

### Answer by username_5 on 2014-05-07. Score: 12

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.


---

