Timeline for Relation of Space and Time in Complexity?
Current License: CC BY-SA 3.0
Post Revisions
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 28, 2014 at 17:27 | comment | added | vzn | there are many other neat thms that connect & show tight coupling between Time/Space complexity, there are many angles on it, would like to compile a comprehensive list, know of a few, might work on this sometime... see also we believe a lot but can prove little by rjlipton for some interesting connections | |
| Feb 28, 2014 at 17:03 | comment | added | EthanLWillis | That's really what I'm looking for. I want to read something that discusses the relation of space/time complexity. But I've been unable to find anything. | |
| Feb 28, 2014 at 7:38 | history | tweeted | twitter.com/#!/StackCompSci/status/439303527652151296 | ||
| Feb 28, 2014 at 4:20 | comment | added | vzn | "I'd also appreciate any reading you can suggest to me on time/space tradeoffs and NTMs versus DTMs." 1) P vs NP conjecture wikipedia 1) Golden ticket: P, NP, search for the impossible Fortnow | |
| Feb 28, 2014 at 4:15 | comment | added | vzn | this is a very complex topic, full of many nearby open questions, wish there was a nice survey/overview somewhere. Time/Space are tightly coupled in many important thms but often studied separately in a reductionistic/somewhat disconnected way and nondeterminism adds an extra dimension. it would make another great question... | |
| Feb 28, 2014 at 0:04 | vote | accept | EthanLWillis | ||
| Feb 27, 2014 at 21:03 | answer | added | David Richerby | timeline score: 5 | |
| Feb 27, 2014 at 21:03 | review | First posts | |||
| Feb 27, 2014 at 21:24 | |||||
| Feb 27, 2014 at 20:46 | history | asked | EthanLWillis | CC BY-SA 3.0 |