P est-il égal à l'intersection de toutes les classes temporelles superpolynomiales?

Appelons une fonction superpolynomiale si vaut pour chaque c> 0 .$f(n)$ $\lim_{n\rightarrow\infty} n^c/f(n)=0$$c>0$

Il est clair que pour tout langage il contient pour chaque temps superpolynomial lié f (n) . Je me demande si l'inverse de cette affirmation est également vrai? Autrement dit, si nous connaissons L \ in {\ mathsf {DTIME}} (f (n)) pour chaque limite de temps superpolynomiale f (n) , cela implique-t-il L \ in {\ mathsf P} ? En d'autres termes, est-il vrai que {\ mathsf P} = \ cap_f {\ mathsf {DTIME}} (f (n)) où l'intersection est reprise sur chaque superpolynôme f (n) .$L\in {\mathsf P}$$L\in {\mathsf {DTIME}}(f(n))$$f(n)$$L\in {\mathsf {DTIME}}(f(n))$$f(n)$$L\in {\mathsf P}$

Oui.

En fait, d'après le théorème de l'Union McCreight-Meyer (Théorème 5.5 de McCreight et Meyer, 1969 , version gratuite ici ), un résultat qui, je pense, est dû à Manuel Blum , il existe une seule fonction telle que . Cette fonction est nécessairement superpolynomiale, mais "à peine".$f$$\mathsf{P} = \mathsf{DTIME}(f(n))$

Le théorème s'applique plus généralement à toute mesure de complexité Blum et à toute classe d'union où est un ensemble de ce fonctions calculables totales. (Un ensemble de fonctions est ce s'il y a une seule fonction partielle calculable telle que où . L'auto-limitation signifie que pour chaque sous-ensemble fini , il y a une fonction dans qui domine tout presque partout. "$\Phi$$\bigcup_{f \in S} \mathsf{BLUM}_{\Phi}(f(n))$$S$$S$$F(i,\vec{x})$$S = \{f_i(\vec{x}) | i \in \mathbb{N}\}$$f_i(\vec{x}) := F(i,\vec{x})$S g ∈ S 0 B L U M Φ$S_0 \subset S$$S$$g \in S_0$$\mathsf{BLUM}_{\Phi}$"est une notation que je n'ai jamais vue auparavant, mais je l'aime :) - Je l'utilise pour l' analogue délimité d'une classe de complexité limitée dans le temps.)$\Phi$