3
$\begingroup$

For language $L$, we have $\forall\varepsilon > 0,L\in\mathcal{O}(n^\varepsilon)$. What is the class of $L$?

It is obvious that $L\in$ polynomials. Is there a smaller class for $L$? For example, $L\in\mathcal{O}(\lg(n))$ or $L\in\mathcal{O}(\mathrm{polylog}(n))$?

$\endgroup$
  • $\begingroup$ Are you sure you don't mean $\forall \varepsilon > 1$? $\endgroup$ – Solomonoff's Secret Jun 28 '18 at 12:55
  • $\begingroup$ @Solomonoff'sSecret no it is greater than zero. for example any language in O(lg n) has above conditions. but I want greater complexity (than logarithmic) class with above conditions if exists. $\endgroup$ – Mohsen Ghorbani Jun 28 '18 at 13:00
  • 2
    $\begingroup$ Sometimes the notation $O(n^{o(1)})$ is used for this. $\endgroup$ – Yuval Filmus Jun 28 '18 at 14:20
  • $\begingroup$ @YuvalFilmus Wouldn't that mean $\{f : \exists \varepsilon, f\in O(n^\varepsilon)\}$ while the class in the question is $\{f:\forall \varepsilon, f\in O(n^\varepsilon)\}$? $\endgroup$ – xavierm02 Jun 28 '18 at 14:41
  • $\begingroup$ No, $f = O(n^{o(1)})$ if there exists $g = o(1)$ such that $f = O(n^g)$. If $f$ is a function satisfying your condition, let $g = \log_n f$. For all $\epsilon > 0$ there exists $C_\epsilon$ such that $f \leq C_\epsilon n^\epsilon$, and so $g \leq \log_n C_\epsilon + \epsilon$. In particular, for every $\epsilon > 0$ we can find $n$ large enough so that eventually $g < 2\epsilon$. Hence $g = o(1)$. $\endgroup$ – Yuval Filmus Jun 28 '18 at 14:45
3
$\begingroup$

Define $$A := \bigcap_{\varepsilon > 0} O(n^\varepsilon) = \bigcap_{i \in \mathbb{N}} O(n^\frac{1}{i}).$$ This complexity class is analogous to $$B := \bigcap_{i \in \mathbb{N}} \Omega(n^i),$$ the class of super-polynomial functions, in the sense that if $f$ is strictly increasing, $f \in A \Leftrightarrow f^{-1} \in B$. There isn't a "nice" description of $B$ so you wouldn't expect a "nice" description of $A$.

Note that $e^\sqrt[i]{n} \in B$ so $\log^i n \in A$.

$\endgroup$

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.