"Squeezing in" between polynomial and exponential

47 Views Asked by At

Let $\mathbb{R}_+$ denote the set of positive reals. Let $\mathbb{R}_+^{\mathbb{R}_+}$ denote the set of all functions $f:\mathbb{R}_+\to \mathbb{R}_+$. For $f,g: \mathbb{R}_+\to \mathbb{R}_+$ we say $f\leq^* g$ if there is $N\in\mathbb{N}$ such that $f(x)\leq g(x)$ for all $x\geq N$.

Let $A=\{ f\in\mathbb{R}_+^{\mathbb{R}_+}: \exists n\in\mathbb{N}: f(x) = x^n \text{ for all x}\in \mathbb{R}_+\}$ and let $B=\{ f\in\mathbb{R}_+^{\mathbb{R}_+}: \exists \varepsilon\in\mathbb{R}_+: f(x) = (1+\varepsilon)^x \text{ for all x}\in \mathbb{R}_+\}$.

Question. Is there $s\in\mathbb{R}_+^{\mathbb{R}_+}$ such that for all $a\in A$ and for all $b\in B$ we have $a\leq^* s\leq^* b$?

Soft question. (Just out of interest; not needed for acceptance of answer.) If "yes" to the main question above, is there a "natural" problem that is not polynomial, but solvable in "time $s$"?