Timeline for unbounded complexity
Current License: CC BY-SA 3.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 2, 2013 at 18:17 | history | edited | François G. Dorais | CC BY-SA 3.0 |
typo
|
| Sep 2, 2013 at 14:06 | comment | added | Joseph O'Rourke | @Joel: Apologies; I stand corrected. | |
| Sep 2, 2013 at 14:00 | comment | added | Joel David Hamkins | Ken, I think you mean Turing. | |
| Sep 2, 2013 at 13:59 | answer | added | Emil Jeřábek | timeline score: 1 | |
| Sep 2, 2013 at 13:57 | comment | added | Joel David Hamkins | @JosephO'Rourke, complexity theory questions are on-topic here at MO. | |
| Sep 2, 2013 at 13:56 | answer | added | Joel David Hamkins | timeline score: 2 | |
| Sep 2, 2013 at 13:41 | answer | added | Denis | timeline score: 3 | |
| Sep 2, 2013 at 13:33 | comment | added | François G. Dorais | Does "is in $O(f(n))$" mean that deciding whether a string is in $L$ can be computed in time $O(f(n))$ where $n$ is the length of the string? Does the language have a finite alphabet? (If both answers are yes, then the answer is trivially yes by taking $f(n)$ to be the maximum computing time of the decision algorithm over strings of length $n$. This is computable since the alphabet is finite and there are only finitely many strings of length $n$.) | |
| Sep 2, 2013 at 13:22 | review | First posts | |||
| Sep 2, 2013 at 13:25 | |||||
| Sep 2, 2013 at 13:10 | comment | added | Joseph O'Rourke | A better forum for this question is Theoretical Computer Science. | |
| Sep 2, 2013 at 13:04 | history | asked | ken | CC BY-SA 3.0 |