# Is P equal to the intersection of all superpolynomial time classes?

Let us call a function $f(n)$ superpolynomial if $\lim_{n\rightarrow\infty} n^c/f(n)=0$ holds for every $c>0$.

It is clear that for any language $L\in {\mathsf P}$ it holds that $L\in {\mathsf {DTIME}}(f(n))$ for every superpolynomial time bound $f(n)$. I wonder, wether the converse of this statement is also true? That is, if we know $L\in {\mathsf {DTIME}}(f(n))$ for every superpolynomial time bound $f(n)$, does it imply $L\in {\mathsf P}$? In other words, is it true that $${\mathsf P} = \cap_f {\mathsf {DTIME}}(f(n))$$ where the intersection is taken over every superpolynomial $f(n)$.

• A general advice about writing questions is that you should make your question (stated in the easiest way to understand) your title. – Kaveh Sep 18 '14 at 3:12

Yes.

In fact, by the McCreight-Meyer Union Theorem (Theorem 5.5 of McCreight and Meyer, 1969, free version here) a result of that I believe is due to Manuel Blum, there is a single function $f$ such that $\mathsf{P} = \mathsf{DTIME}(f(n))$. This function is necessarily superpolynomial, but "just barely."

The theorem applies more generally to any Blum complexity measure $\Phi$ and any union class $\bigcup_{f \in S} \mathsf{BLUM}_{\Phi}(f(n))$ where $S$ is a c.e., self bounded set of total computable functions. (A set of functions $S$ is c.e. if there is a single partial computable function $F(i,\vec{x})$ such that $S = \{f_i(\vec{x}) | i \in \mathbb{N}\}$ where $f_i(\vec{x}) := F(i,\vec{x})$. Self-bounded means that for every finite subset $S_0 \subset S$, there is a function in $S$ that dominates all $g \in S_0$ almost everywhere. "$\mathsf{BLUM}_{\Phi}$" is a notation I haven't seen before, but I like it :) - I'm using it for the $\Phi$-bounded analog of a time-bounded complexity class.)

• I think the catch is that $f$ is not time-constructible. – Sasho Nikolov Sep 18 '14 at 3:52
• Josh, does Manuel's result use something special about polynomial time? I mean does it also apply to similar time union classes? – Kaveh Sep 18 '14 at 4:12
• I find the following fact fascinating: while obviously there is no smallest superpolynomial function, yet there is a smallest complexity class among those that are defined by a superpolynomial time bound. Moreover, this class is equal to P, in which nothing is superpolynomial. – Andras Farago Sep 20 '14 at 3:56
• @AndrasFarago: It is indeed fascinating, but (I think) no stranger than the Borodin-Trakhtenbrot Gap Theorem (en.wikipedia.org/wiki/Gap_theorem). – Joshua Grochow Sep 20 '14 at 18:27
• @SashoNikolov: I'd have to think more about that one, but after just one moment's thought I think it has more to do with the fact that one can simulate/diagonalize over TMs, which has more to do with their countable nature and the existence of universal machines... In particular, the axioms for a Blum complexity measure require that the various functions that define the Blum measure be computable or partial computable, and this is key in all these theorems. And note that McCreight-Meyer requires the set S itself to be a c.e. set of functions, also key. – Joshua Grochow Sep 20 '14 at 23:36