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.).

  • $\begingroup$ Have you tried using the standard methods? Where does that lead you? $\endgroup$ – Raphael Dec 13 '16 at 22:00
  • $\begingroup$ @Raphael this is not a query of computation. It is a query of notation. $\endgroup$ – T.... Dec 13 '16 at 22:00
  • 3
    $\begingroup$ 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. $\endgroup$ – 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.

| cite | improve this answer | |
  • $\begingroup$ So I am wrong? $\cap_{f(n)\in\omega(1)}D(n^{f(n)})\subsetneq\cap_{\epsilon>0}C(n^{n^\epsilon})$ is correct? $\endgroup$ – T.... Dec 14 '16 at 19:34
  • $\begingroup$ I don't know, you tell me. $\endgroup$ – Yuval Filmus Dec 14 '16 at 20:07
  • $\begingroup$ 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. $\endgroup$ – T.... Dec 14 '16 at 20:57
  • $\begingroup$ Have you read my answer? $\endgroup$ – Yuval Filmus Dec 14 '16 at 20:58
  • $\begingroup$ @YuvalFilms yes. updated my comment. $\endgroup$ – T.... Dec 14 '16 at 20:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.