Timeline for Do runtimes for P require EXP resources to upper-bound? ... are concrete examples known? (answer: yes and yes)
Current License: CC BY-SA 2.5
2 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 3, 2011 at 14:17 | comment | added | John Sidles | Over on TCS StackExchange, Luca Trevisan has <a href="cstheory.stackexchange.com/questions/4704/… an explicit construction</a> that (if I grasp it correctly) yields a class of algorithms in P for which runtime estimation is harder-than-P ... it will take me a few days to digest Luca's ideas, and their implications for the questions at-hand. | |
| Feb 3, 2011 at 3:28 | history | answered | Noah Stein | CC BY-SA 2.5 |