patternMinor
What is complexity class language $L$ such that $\forall\varepsilon > 0,L\in\mathcal{O}(n^\varepsilon)$?
Viewed 0 times
suchforallwhatmathcallanguagethatclassvarepsiloncomplexity
Problem
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))$?
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))$?
Solution
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$.
$$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$.
Context
StackExchange Computer Science Q#93621, answer score: 3
Revisions (0)
No revisions yet.