Timeline for How can you prove that a problem is not solvable in a certain time complexity?
Current License: CC BY-SA 3.0
19 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 19, 2013 at 7:54 | history | tweeted | twitter.com/#!/StackCSTheory/status/325155454927912960 | ||
| Apr 17, 2013 at 18:57 | answer | added | Ashwinkumar B V | timeline score: 4 | |
| Apr 15, 2013 at 15:45 | comment | added | Tiddo | I'm pretty sure that I should've asked this on cs instead of cstheory. I'm still an undergrad and I just wanted to learn a bit more about complexity theory than the undergrad complexity theory course provided by my university teaches me. Anyway, I got a lot of new information and topics I can dive into from all your replies so it helped me a lot. My apologies for asking this on the wrong stackexchange site. | |
| Apr 15, 2013 at 15:05 | comment | added | vzn | imho, not research level because the question seems not to be aware of the basic time/space hierarchy thms. for example clearly if a problem has a lower bound of space complexity DSPACE(f(n)) then it has time complexity DTIME(f(n)). therefore a problem that requires EXPSPACE requires EXPTIME and an example of this is Meyer & Stockmeyers proof: "The equivalence problem for regular expressions with squaring requires exponential space". recommend migrate to cs.se | |
| Apr 15, 2013 at 6:49 | comment | added | Sasho Nikolov | it might be good to focus the question w.r.t. a model of computation. if restricted models (=not polytime equivalent to a multi tape TM) are allowed, then the question might be too broad. | |
| Apr 15, 2013 at 6:17 | answer | added | David Eppstein | timeline score: 14 | |
| Apr 15, 2013 at 3:57 | comment | added | Jeffε | I strongly oppose closing. This is not only a research-level question, it is arguably THE research-level question! | |
| Apr 14, 2013 at 13:33 | comment | added | András Salamon | See en.wikipedia.org/wiki/Time_hierarchy_theorem | |
| Apr 14, 2013 at 10:04 | review | Close votes | |||
| Apr 19, 2013 at 3:01 | |||||
| Apr 14, 2013 at 9:35 | vote | accept | Tiddo | ||
| Apr 14, 2013 at 9:34 | history | edited | Tiddo | CC BY-SA 3.0 |
added 6 characters in body
|
| Apr 14, 2013 at 9:29 | comment | added | Tiddo | @Jeremy - Thank you, you're absolutely right. I should've asked this question on cs.stackexchange.com I guess. | |
| Apr 14, 2013 at 8:40 | answer | added | J..y B..y | timeline score: 6 | |
| Apr 14, 2013 at 8:10 | comment | added | J..y B..y | I think some people down voted your question because they believe that it is not a research-level question. (see cstheory.stackexchange.com/faq and in particular the first two answered questions, "What kind of questions can I ask here?" and "My question is not a research-level question in TCS, where can I ask it?"). | |
| S Apr 13, 2013 at 19:19 | history | suggested | CommunityBot | CC BY-SA 3.0 |
fixing the names of complexity classes
|
| Apr 13, 2013 at 19:11 | review | Suggested edits | |||
| S Apr 13, 2013 at 19:19 | |||||
| Apr 13, 2013 at 18:23 | review | First posts | |||
| Apr 14, 2013 at 8:10 | |||||
| Apr 13, 2013 at 18:21 | history | edited | Tiddo | CC BY-SA 3.0 |
added 185 characters in body
|
| Apr 13, 2013 at 18:07 | history | asked | Tiddo | CC BY-SA 3.0 |