# On asymptotic complexity class notation?

Is the class of problems with complexity $O(n^{n^\epsilon})$ at every $\epsilon>0$ same as class of problems with complexity $O(n^{f(n)})$ at every $f(n)\in\omega(1)$ and hence both classes are equivalent to $\mathsf P$ ($n$ is number of input bits)?

(This is my view. Denote $C(n^{n^\epsilon})$ to be class of problems solvable in $O(n^{n^\epsilon})$ at every $\epsilon>0$ and let $D(n^{f(n)})$ be class of problems solvable in $O(n^{f(n)})$ at every $f(n)$ in $\omega(1)$. Does $\cap_{f(n)\in\omega(1)}D(n^{f(n)})=\cap_{\epsilon>0}C(n^{n^\epsilon})$ hold? $\forall n\in\Bbb N\wedge\forall\delta>0 \exists\epsilon>0:n^\epsilon<1+\delta$ and so $C(n^{n^\epsilon})$ is smaller than $D(n^{f(n)})$ at every $f(n)$ in $\omega(1)$. However for every $\epsilon>0$ there is an $f(n)\in\omega(1)$ such that $f(n)<n^\epsilon$ at large enough $n\in\Bbb N$ and so $D(n^{f(n)})$ at any $f(n)$ in $\omega(1)$ is smaller than $C(n^{n^\epsilon})$. We then conclude both $O(n^{n^\epsilon})$ and $O(n^{f(n)})$ at any $f(n)\in\omega(1)$ are morally equal. Since $O(n^{f(n)})$ at any $f(n)\in\omega(1)$ is same as $\mathsf P$ we have the notation.).

• Have you tried using the standard methods? Where does that lead you? – Raphael Dec 13 '16 at 22:00
• @Raphael this is not a query of computation. It is a query of notation. – T.... Dec 13 '16 at 22:00
• I don't think so. You are forming a hypothesis about two Landau classes, namely that one is included in the other -- that something you prove, not denote. – Raphael Dec 13 '16 at 22:04

The time hierarchy theorem shows that there are problems which can be solved in time $O(n^{\log n})$ but not in time $O(n^{\log\log n})$. These problems can be solved in time $O(n^{n^\epsilon})$ for any $\epsilon > 0$, but not in polynomial time.
• So I am wrong? $\cap_{f(n)\in\omega(1)}D(n^{f(n)})\subsetneq\cap_{\epsilon>0}C(n^{n^\epsilon})$ is correct? – T.... Dec 14 '16 at 19:34
• 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. – T.... Dec 14 '16 at 20:57