¿Es P igual a la intersección de todas las clases de tiempo superpolinomiales?

$f(n)$ $\lim_{n\rightarrow\infty} n^c/f(n)=0$$c>0$

Está claro que para cualquier lenguaje $L\in {\mathsf P}$ mantiene que $L\in {\mathsf {DTIME}}(f(n))$ para cada límite de tiempo superpolinómico $f(n)$ . Me pregunto si lo contrario de esta afirmación también es cierto. Es decir, si conocemos $L\in {\mathsf {DTIME}}(f(n))$ para cada límite de tiempo superpolinómico $f(n)$ , ¿implica $L\in {\mathsf P}$ ? En otras palabras, ¿es cierto que

Sí.

De hecho, según el Teorema de la Unión McCreight-Meyer (Teorema 5.5 de McCreight y Meyer, 1969 , versión gratuita aquí ), como resultado de eso, creo que se debe a Manuel Blum , hay una única función $f$ tal que $\mathsf{P} = \mathsf{DTIME}(f(n))$ . Esta función es necesariamente superpolinómica, pero "apenas".

El teorema se aplica más generalmente a cualquier medida de complejidad de Blum $\Phi$ y cualquier clase de unión $\bigcup_{f \in S} \mathsf{BLUM}_{\Phi}(f(n))$ donde $S$ es un conjunto ce de Total de funciones computables. (Un conjunto de funciones $S$ es ce si hay una sola función computable parcial $F(i,\vec{x})$ tal que $S = \{f_i(\vec{x}) | i \in \mathbb{N}\}$ donde $f_i(\vec{x}) := F(i,\vec{x})$ . Auto-limitado significa que por cada subconjunto finito $S_0 \subset S$ , hay una función en $S$ que domina todos los $g \in S_0$ casi en todas partes ". $\mathsf{BLUM}_{\Phi}$"es una notación que no había visto antes, pero me gusta :) - Lo estoy usando para el análogo limitado por $\Phi$ de una clase de complejidad limitada por el tiempo).