1
$\begingroup$

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

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

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
12
  • $\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$
    – Turbo
    Commented Dec 14, 2016 at 19:34
  • $\begingroup$ I don't know, you tell me. $\endgroup$ Commented Dec 14, 2016 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$
    – Turbo
    Commented Dec 14, 2016 at 20:57
  • $\begingroup$ Have you read my answer? $\endgroup$ Commented Dec 14, 2016 at 20:58
  • $\begingroup$ @YuvalFilms yes. updated my comment. $\endgroup$
    – Turbo
    Commented Dec 14, 2016 at 20:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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