Timeline for Learning about EXPTIME and EXPSPACE
Current License: CC BY-SA 2.5
14 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 20, 2011 at 16:50 | vote | accept | Matt Groff | ||
| Feb 12, 2011 at 2:20 | answer | added | Bin Fu | timeline score: 1 | |
| Feb 10, 2011 at 23:50 | comment | added | Tsuyoshi Ito | From your comment, it seems to me that you are interested in works on algorithms (for some natural problems) which take exponential time and/or space rather than the complexity-theoretic aspect of the classes EXP and EXPSPACE. (If this is the case, I think that the correct tag is [ds.algorithms] rather than [cc.complexity-theory].) That is much more reasonable than “Tell me anything about EXP and EXPSPACE,” but I am afraid that still there might be too many works satisfying your criteria. | |
| Feb 10, 2011 at 23:45 | comment | added | Matt Groff | One direction of study that I'm interested in is viewing papers on problems considered in one of these classes, and discussing the runtimes and analysis. I've had fun considering the designs of algorithms to solve tough problems. So I'm wondering what types of problems are associated with these two classes. I'll try to provide a more descriptive inquiry soon... | |
| Feb 10, 2011 at 14:41 | comment | added | John Sidles | I have found it plenty challenging to construct concrete examples of the complexity classes that an answer by Luca Trevisan references: "problems in NE that require doubly-exponential time to be solved", and surely I am not alone in liking to see concrete examples of complexity classes. So if this question were amended to request references that include multiple concrete example, then I would up-vote it. See the MathOverflow link to Trevisan's answer: "cstheory.stackexchange.com/questions/4704/…" | |
| Feb 10, 2011 at 9:52 | comment | added | András Salamon | Following on from Kaveh's comment, qwiki.stanford.edu/index.php/Complexity_Zoo:E#exp and qwiki.stanford.edu/index.php/Complexity_Zoo:E#expspace would be my canonical points of departure. | |
| Feb 10, 2011 at 8:37 | comment | added | Kaveh | Matt, I think the question is too general in the current form. It would be better if you give some motivation and be more specific about what you want to know about them and why. In the current form the answer is "check the complexity zoo". | |
| Feb 10, 2011 at 8:22 | history | tweeted | twitter.com/#!/StackCSTheory/status/35614589152399360 | ||
| Feb 10, 2011 at 8:15 | comment | added | Suresh Venkat | well it is a reference request, so it seems more on topic than off. For example, consider also Matt's question k-SAT (cstheory.stackexchange.com/questions/4314/…) which was well received | |
| Feb 10, 2011 at 8:04 | history | edited | Hsien-Chih Chang 張顯之 |
edited tags
|
|
| S Feb 10, 2011 at 7:33 | history | suggested | Huck Bennett |
Added "reference-request" tag, as that's the nature of the question.
|
|
| Feb 10, 2011 at 7:22 | comment | added | Tsuyoshi Ito | Too vague. What do you want to know about EXP and EXPSPACE? I hope that your question is research-level, because otherwise it will not belong on this website. | |
| Feb 10, 2011 at 7:18 | review | Suggested edits | |||
| S Feb 10, 2011 at 7:33 | |||||
| Feb 10, 2011 at 7:15 | history | asked | Matt Groff | CC BY-SA 2.5 |