Timeline for Analogues of P vs. NP in the history of mathematics
Current License: CC BY-SA 3.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 14, 2014 at 22:00 | history | made wiki | Post Made Community Wiki by Todd Trimble | ||
| Mar 14, 2014 at 17:45 | comment | added | Benjamin Steinberg | It did take a long time to prove subexponential growth properly contains polynomial growth. | |
| Mar 14, 2014 at 17:45 | comment | added | Benjamin Steinberg | The dichotomy is not so obvious and is in fact due to van den Dries and Wilkie. There are semigroups whose growth oscillates between just above quadratic and exponential. van den Dries and Wilkie showed if the growth of a group is bounded by a polynomial on an infinite subsequence then the group is virtually nilpotent. | |
| Mar 14, 2014 at 15:21 | comment | added | Scott Aaronson | But in Gromov's case, the existence of the dichotomy (between groups of polynomial growth and groups of superpolynomial growth) was obvious, right? And Gromov's contribution was to give an alternate characterization of that dichotomy. So this doesn't seem analogous to P vs. NP at all. I'm looking for cases where a long-conjectured dichotomy between two large classes of objects was either proved to be real or proved to be entirely illusory. | |
| Mar 14, 2014 at 9:02 | history | answered | Mikhail Katz | CC BY-SA 3.0 |