# Is there a difference between extremely slow growing functions and constants with respect to computable functions?

So let's say we have the function $$f(n)$$ that gives $$k$$ such that $$k$$ is the smallest number that gives a busy beaver function $$B$$ value from input $$k$$ that is greater than $$n$$. Or more succinctly the smallest $$k$$ with $$B(k) > n$$. Can there be computable functions that are not in time complexity class $$O(n^c)$$ for some constant $$c$$ but that are in $$O(n^{f(n)})$$. And by extension, is it true that $$P = O(n^{f(n)})$$?

• Busy Beaver can't be computed, and thus also $f$ cannot be computed (think of a way knowing $f$ to compute BB). I don't understand how this has to do anything with the rest of the question though. And no, if $f$ is constant then $O(n^{f(n)})$ is like $O(n^c)$, which does not contain all $P$ Jul 28 at 10:06
• @nirshahar I think I wasn't clear enough, I didn't mean $f$ would be constant. I also did not mean to assert that $f$ is computable. I meant to say that given such slow growing $f$, then complexity class $O(n^{f(n)})$ must contain all functions $O(n^c)$ for constant $c$, since $f$ grows and $c$ doesn't. I was just wondering if such a complexity class for computable functions contains anything other than polynomial-time functions? Jul 28 at 10:13
• If $f$ grows fast enough (e.g, at least $\omega(\log(n))$), then yea - by the time hierarchy theorem Jul 28 at 10:18
• @nirshahar Yes, I think I've made it a little more clear, but I specifically meant to ask about the case where $f$ grows slower than any computable function that is not a constant. Jul 28 at 10:22
• Then $f$ must be constant, otherwise it would need to grow slower than $\log(f(n))$, which is clearly much slower-growing than $f(n)$ itself Jul 28 at 10:29

Your definition of $$f$$ is $$f(n) > k \Longleftrightarrow B(k) \leq n.$$ Now suppose that $$M$$ is a Turing machine that runs in time $$C n^{f(n)}$$ but not in polynomial time. Since $$M$$ does not run in polynomial time, for every $$k$$ we can find $$n$$ such that its running time for some input of length $$n$$ is more than $$C n^k$$; this can be done effectively, by going over all strings. Having found such $$n$$, we can conclude that $$Cn^k < Cn^{f(n)}$$ and so $$f(n) > k$$, implying that $$B(k) \leq n$$. Since we can compute such $$n$$ for every $$k$$, this allows us solve the halting problem, showing that no such machine $$M$$ can exist.
As for your second question, if $$g(n) \to \infty$$ then every polytime machine trivially runs in time $$O(n^{g(n)})$$. Indeed, if the machine runs in time $$Cn^C$$ then since $$g(n) \to \infty$$, we have $$g(n) \geq C$$ for large $$n$$, and so $$Cn^C = O(n^{g(n)})$$. This shows that every language in $$\mathsf{P}$$ also lies in $$\mathsf{TIME}(O(n^{f(n)})) = \bigcup_{C \in \mathbb{N}} \mathsf{TIME}(Cn^{f(n)})$$ (often we use $$\mathsf{TIME}(n^{f(n)})$$ to denote this class). As we have seen above, the converse also holds, and so $$\mathsf{P} = \mathsf{TIME}(O(n^{f(n)}))$$.