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$ Commented Dec 13, 2016 at 22:00
  • $\begingroup$ @Raphael this is not a query of computation. It is a query of notation. $\endgroup$ 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$ 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$ 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$ 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$ Commented Dec 14, 2016 at 20:58

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.