Timeline for On asymptotic complexity class notation?
Current License: CC BY-SA 3.0
15 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 15, 2016 at 7:46 | comment | added | Yuval Filmus | Nevertheless, this is a new question, and you should ask it as such. That's how this platform works. If you find it hard to frame it, do your best. | |
| Dec 15, 2016 at 7:06 | comment | added | Turbo | @yucalfilmus I do not know how to frame the problem properly and so I posted as a comment. | |
| Dec 15, 2016 at 7:01 | comment | added | Yuval Filmus | That's a separate question. | |
| Dec 15, 2016 at 5:53 | comment | added | Turbo | is there a more strict natural formulation that would equal link a function of $n$ and $\epsilon$ with $f(n)\in\omega(1)$ (as described)? | |
| Dec 14, 2016 at 23:13 | comment | added | Turbo | So $\cap_{f(n)\in\omega(1)}D(n^{f(n)})\subsetneq C(n^{\log n})\subsetneq C(n^{n^{\epsilon}})$ is the correct way to interpret? ok. | |
| Dec 14, 2016 at 23:05 | vote | accept | Turbo | ||
| Dec 14, 2016 at 23:02 | comment | added | Yuval Filmus | It all boils down to the fact that there are unbounded functions which are $O(n^\epsilon)$ for all $\epsilon > 0$, for example $\log n$. | |
| Dec 14, 2016 at 22:57 | comment | added | Turbo | I am not fixing $\epsilon>0$ when I say $\cap_{\epsilon>0}$. | |
| Dec 14, 2016 at 20:58 | comment | added | Turbo | @YuvalFilms yes. updated my comment. | |
| Dec 14, 2016 at 20:58 | comment | added | Yuval Filmus | Have you read my answer? | |
| Dec 14, 2016 at 20:57 | comment | added | Turbo | both classes seem same to me and equal to $\mathsf P$. But as you say $C(n^{n^\epsilon})$ does not seem to be $\mathsf{P}$. Hence my query. | |
| Dec 14, 2016 at 20:07 | comment | added | Yuval Filmus | I don't know, you tell me. | |
| Dec 14, 2016 at 20:07 | history | edited | Yuval Filmus | CC BY-SA 3.0 |
added 1 character in body
|
| Dec 14, 2016 at 19:34 | comment | added | Turbo | So I am wrong? $\cap_{f(n)\in\omega(1)}D(n^{f(n)})\subsetneq\cap_{\epsilon>0}C(n^{n^\epsilon})$ is correct? | |
| Dec 14, 2016 at 19:09 | history | answered | Yuval Filmus | CC BY-SA 3.0 |