Timeline for Examples of Super-polynomial time algorithmic/induction proofs?
Current License: CC BY-SA 2.5
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 26, 2020 at 11:54 | answer | added | Tony Huynh | timeline score: 1 | |
| Jul 14, 2016 at 12:36 | comment | added | Sasho Nikolov | Banaszczyk's theorem from discrepancy theory has this structure. It's an inductive proof that takes a linear number of steps, but at each step it doubles the complexity of the object it's dealing with. If you are interested (6 years after you asked the quesiton...) I can write more details. | |
| Dec 30, 2013 at 22:28 | answer | added | none | timeline score: 1 | |
| May 25, 2011 at 19:20 | answer | added | Gil Kalai | timeline score: 2 | |
| Jul 30, 2010 at 22:26 | answer | added | Noah Stein | timeline score: 4 | |
| Jul 30, 2010 at 16:19 | history | asked | miforbes | CC BY-SA 2.5 |