21
$\begingroup$

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

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

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

$\endgroup$
  • 12
    $\begingroup$ I think the catch is that $f$ is not time-constructible. $\endgroup$ – Sasho Nikolov Sep 18 '14 at 3:52
  • 4
    $\begingroup$ Josh, does Manuel's result use something special about polynomial time? I mean does it also apply to similar time union classes? $\endgroup$ – Kaveh Sep 18 '14 at 4:12
  • 2
    $\begingroup$ 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. $\endgroup$ – Andras Farago Sep 20 '14 at 3:56
  • 2
    $\begingroup$ @AndrasFarago: It is indeed fascinating, but (I think) no stranger than the Borodin-Trakhtenbrot Gap Theorem (en.wikipedia.org/wiki/Gap_theorem). $\endgroup$ – Joshua Grochow Sep 20 '14 at 18:27
  • 2
    $\begingroup$ @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. $\endgroup$ – Joshua Grochow Sep 20 '14 at 23:36

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.