P é igual à interseção de todas as classes de tempo superpolinomiais?

Vamos chamar uma função superpolinomial se for válido para cada c> 0 .$f(n)$ c > $\lim_{n\rightarrow\infty} n^c/f(n)=0$$c>0$

É claro que, para qualquer idioma $L\in {\mathsf P}$ ele sustenta que $L\in {\mathsf {DTIME}}(f(n))$ para todo tempo superpolinomial ligado a $f(n)$ . Será que o inverso dessa afirmação também é verdadeiro? Ou seja, se conhecemos $L\in {\mathsf {DTIME}}(f(n))$ para cada tempo superpolinomial ligado a $f(n)$ , isso implica $L\in {\mathsf P}$ ? Em outras palavras, é verdade que

Sim.

De fato, pelo Teorema da União McCreight-Meyer (Teorema 5.5 de McCreight e Meyer, 1969 , versão gratuita aqui ), resultado do que acredito ser devido a Manuel Blum , há uma única função $f$ tal que $\mathsf{P} = \mathsf{DTIME}(f(n))$ . Essa função é necessariamente superpolinomial, mas "apenas por pouco".

O teorema se aplica de maneira mais geral a qualquer medida de complexidade de Blum $\Phi$ e a qualquer classe de união $\bigcup_{f \in S} \mathsf{BLUM}_{\Phi}(f(n))$ que $S$ é um conjunto de limites auto-limitados de funções computáveis ​​totais. (Um conjunto de funções $S$ é ce se houver uma única função computável parcial $F(i,\vec{x})$ tal que $S = \{f_i(\vec{x}) | i \in \mathbb{N}\}$ onde $f_i(\vec{x}) := F(i,\vec{x})$ . Auto-limitado significa que para cada subconjunto finito $S_0 \subset S$ , existe uma função em $S$ que domina todos os $g \in S_0$ em quase todos os lugares. " $\mathsf{BLUM}_{\Phi}$"é uma notação que nunca vi antes, mas gosto :) - estou usando-a para o análogo $\Phi$ bounded de uma classe de complexidade com limite de tempo.)