Ist P gleich dem Schnittpunkt aller superpolynomialen Zeitklassen?

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

Es ist klar , dass für jede Sprache gilt , daß für jede Zeit gebunden superpolynomielle . Ich frage mich, ob das Gegenteil dieser Aussage auch zutrifft. Das heißt, wenn wir für jede superpolynomielle , impliziert dies ? Mit anderen Worten, ist es wahr, dass wobei der Schnittpunkt jedes Superpolynoms .$L\in {\mathsf P}$$L\in {\mathsf {DTIME}}(f(n))$$f(n)$$L\in {\mathsf {DTIME}}(f(n))$$f(n)$$L\in {\mathsf P}$

Ja.

Tatsächlich gibt es nach dem McCreight-Meyer-Union-Theorem (Theorem 5.5 von McCreight und Meyer, 1969 , freie Version hier ) ein Ergebnis, von dem ich glaube, dass es auf Manuel Blum zurückzuführen ist, eine einzige Funktion wie . Diese Funktion ist notwendigerweise superpolynomiell, aber "gerade noch".$f$$\mathsf{P} = \mathsf{DTIME}(f(n))$

Das Theorem gilt allgemeiner für jedes Blum-Komplexitätsmaß und jede Union-Klasse wobei eine ce, selbst begrenzte Menge von ist gesamt berechenbare Funktionen. (Eine Menge von Funktionen ist ce, wenn es eine einzelne partielle berechenbare Funktion so dass wobei . Selbstbegrenzt bedeutet, dass es für jede endliche Teilmenge eine Funktion in , die alle dominiert fast überall. "$\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_0 \subset S$$S$$g \in S_0$$\mathsf{BLUM}_{\Phi}$"ist eine Notation, die ich noch nicht gesehen habe, aber ich mag sie :) - Ich verwende sie für das gebundene Analog einer zeitbegrenzten Komplexitätsklasse.)$\Phi$