Timeline for Super-linear time complexity lower bounds for any natural problem in NP?
Current License: CC BY-SA 4.0
3 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 16, 2021 at 16:31 | history | edited | Sam Nead | CC BY-SA 4.0 |
simplified example problem
|
| Nov 11, 2009 at 1:00 | comment | added | Rune | I wouldn't mind multitape Turing machine, or even the RAM model. The sorting lower bound isn't really a time complexity lower bound. It's a decision tree complexity lower bound. | |
| Nov 11, 2009 at 0:47 | history | answered | Sam Nead | CC BY-SA 2.5 |