24

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

Huck Bennett
  • 4,868
  • 2
  • 33
  • 46
Andras Farago
  • 11,396
  • 37
  • 70
  • 1
    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 03:12

1 Answers1

34

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

Joshua Grochow
  • 37,260
  • 4
  • 129
  • 228
  • 12
    I think the catch is that $f$ is not time-constructible. – Sasho Nikolov Sep 18 '14 at 03:52
  • 4
    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 04:12
  • @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 Sep 18 '14 at 11:18
  • 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 Sep 18 '14 at 15:15
  • 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 Sep 19 '14 at 13:06
  • @AndrasFarago: Yes, nondeterministic time is a Blum complexity measure. – Joshua Grochow Sep 19 '14 at 19:02
  • 2
    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 03:56
  • 2
    @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 Sep 20 '14 at 18:27
  • Does this have anything to do with compactness of complexity measures in some topology or am I completely off base? – Sasho Nikolov Sep 20 '14 at 20:46
  • 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. – Joshua Grochow Sep 20 '14 at 23:36