<p>Yes. </p>

<p>In fact, by the McCreight-Meyer Union Theorem (Theorem 5.5 of <a href="http://dx.doi.org/10.1145/800169.805423">McCreight and Meyer, 1969</a>, <a href="http://reports-archive.adm.cs.cmu.edu/anon/scan/CMU-CS-69-mccreight-meyer.pdf">free version here</a>) <strike>a result of that I believe is due to Manuel Blum</strike>, there is a <em>single</em> function $f$ such that $\mathsf{P} = \mathsf{DTIME}(f(n))$. This function is necessarily superpolynomial, but "just barely."</p>

<p>The theorem applies more generally to any <a href="http://en.wikipedia.org/wiki/Blum_axioms">Blum complexity measure</a> $\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.)</p>

CC BY-SA 3.0
2014-09-18T03:52:30.527Z
I think the catch is that $f$ is not time-constructible.
Sasho Nikolov
CC BY-SA 3.0
2014-09-18T04:12:59.947Z
Josh, does Manuel's result use something special about polynomial time? I mean does it also apply to similar time union classes?
Kaveh
CC BY-SA 3.0
2014-09-18T11:18:32.270Z
@Kaveh: IIRC, the result applies to any union classes, as soon as you have a sequence of complexity bounds $(f_i)$ such that for all $i$ and $n$, $f_i(n)<f_{i+1}(n)$.
Bruno
CC BY-SA 3.0
2014-09-18T15:15:29.820Z
I know that this appears in Oddifreddi's *Classical Recursion Theory* Vol II where there shall be some reference. I don't have it with me yet, and I won't until Monday. If needed, I'll have a look next week.
Bruno
CC BY-SA 3.0
2014-09-19T13:06:11.633Z
Does the Union Theorem also apply to non-deterministic classes? For example, is there a single function $h(n)$, such that NP=NTIME$(h(n))$ holds? My guess would be a "yes" answer to this, because the Blum complexity measure is so general that it probably includes non-deterministic time complexity, as well.
Andras Farago
CC BY-SA 3.0
2014-09-19T19:02:48.060Z
@AndrasFarago: Yes, nondeterministic time is a Blum complexity measure.
Joshua Grochow
CC BY-SA 3.0
2014-09-20T03:56:26.210Z
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
CC BY-SA 3.0
2014-09-20T18:27:02.557Z
@AndrasFarago: It is indeed fascinating, but (I think) no stranger than the Borodin-Trakhtenbrot Gap Theorem (http://en.wikipedia.org/wiki/Gap_theorem).
Joshua Grochow
CC BY-SA 3.0
2014-09-20T20:46:30.150Z
Does this have anything to do with compactness of complexity measures in some topology or am I completely off base?
Sasho Nikolov
CC BY-SA 3.0
2014-09-20T23:36:44.237Z
@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
CC BY-SA 3.0
2014-09-18T02:13:04.667Z
2014-09-18T15:41:06.650Z
2014-09-18T15:41:06.650Z
Joshua Grochow
<p>Let us call a function $f(n)$ <strong>superpolynomial</strong> if $\lim_{n\rightarrow\infty} n^c/f(n)=0$ holds for every $c&gt;0$. </p>

<p>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 <em>every</em> 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)$.</p>

CC BY-SA 3.0
2014-09-18T03:12:13.900Z
A general advice about writing questions is that you should make your question (stated in the easiest way to understand) your title.
Kaveh
<cc.complexity-theory><ds.algorithms><complexity-classes>
Is P equal to the intersection of all superpolynomial time classes?
Andras Farago
# Is P equal to the intersection of all superpolynomial time classes?

(Asked by: username_0 on 2014-09-17)

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

**Tags:** cc.complexity-theory, ds.algorithms, complexity-classes
> **Comments:**
> **username_1**: A general advice about writing questions is that you should make your question (stated in the easiest way to understand) your title.  

---

## 1 answers

### Answer by username_2 on 2014-09-18. Score: 34 | Accepted answer

Yes.

In fact, by the McCreight-Meyer Union Theorem (Theorem 5.5 of [McCreight and Meyer, 1969](http://dx.doi.org/10.1145/800169.805423), [free version here](http://reports-archive.adm.cs.cmu.edu/anon/scan/CMU-CS-69-mccreight-meyer.pdf)) 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](http://en.wikipedia.org/wiki/Blum_axioms) $\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.)

> **Comments:**
> **username_3**: I think the catch is that $f$ is not time-constructible.  
> **username_1**: Josh, does Manuel's result use something special about polynomial time? I mean does it also apply to similar time union classes?  
> **username_4**: @Kaveh: IIRC, the result applies to any union classes, as soon as you have a sequence of complexity bounds $(f_i)$ such that for all $i$ and $n$, $f_i(n)<f_{i+1}(n)$.  
> **username_4**: I know that this appears in Oddifreddi's *Classical Recursion Theory* Vol II where there shall be some reference. I don't have it with me yet, and I won't until Monday. If needed, I'll have a look next week.  
> **username_0**: Does the Union Theorem also apply to non-deterministic classes? For example, is there a single function $h(n)$, such that NP=NTIME$(h(n))$ holds? My guess would be a "yes" answer to this, because the Blum complexity measure is so general that it probably includes non-deterministic time complexity, as well.  
> **username_2**: @AndrasFarago: Yes, nondeterministic time is a Blum complexity measure.  
> **username_0**: 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.  
> **username_2**: @AndrasFarago: It is indeed fascinating, but (I think) no stranger than the Borodin-Trakhtenbrot Gap Theorem (http://en.wikipedia.org/wiki/Gap_theorem).  
> **username_3**: Does this have anything to do with compactness of complexity measures in some topology or am I completely off base?  
> **username_2**: @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.  

---

