Timeline for Arguments for/against Kolmogorov's conjecture about the circuit complexity of P
Current License: CC BY-SA 3.0
3 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 12, 2014 at 23:49 | comment | added | Ryan Williams | 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. | |
| May 12, 2014 at 23:13 | comment | added | Andras Farago | 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? | |
| May 12, 2014 at 1:54 | history | answered | Ryan Williams | CC BY-SA 3.0 |