2
$\begingroup$

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)})$?

$\endgroup$
7
  • $\begingroup$ 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$ $\endgroup$
    – nir shahar
    Jul 28 at 10:06
  • $\begingroup$ @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? $\endgroup$
    – Askeroni
    Jul 28 at 10:13
  • $\begingroup$ If $f$ grows fast enough (e.g, at least $\omega(\log(n))$), then yea - by the time hierarchy theorem $\endgroup$
    – nir shahar
    Jul 28 at 10:18
  • $\begingroup$ @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. $\endgroup$
    – Askeroni
    Jul 28 at 10:22
  • $\begingroup$ 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 $\endgroup$
    – nir shahar
    Jul 28 at 10:29
1
$\begingroup$

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)}))$.

$\endgroup$
1
  • $\begingroup$ I think this answered my question, so this is just a very weird way one could define the class P... $\endgroup$
    – Askeroni
    Jul 29 at 7:09

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.