Apakah P sama dengan persimpangan semua kelas waktu superpolinomial?

Mari kita memanggil fungsi superpolinomial jika ditahan untuk setiap c> 0 .$f(n)$ c > $\lim_{n\rightarrow\infty} n^c/f(n)=0$$c>0$

Jelaslah bahwa untuk bahasa apa pun $L\in {\mathsf P}$ ia berpendapat bahwa $L\in {\mathsf {DTIME}}(f(n))$ untuk setiap batas waktu superpolinomial yang terikat $f(n)$ . Saya bertanya-tanya, apakah kebalikan dari pernyataan ini juga benar? Yaitu, jika kita tahu $L\in {\mathsf {DTIME}}(f(n))$ untuk setiap superpolinomial terikat waktu $f(n)$ , apakah itu menyiratkan $L\in {\mathsf P}$ ? Dengan kata lain, apakah benar bahwa

Iya nih.

Bahkan, oleh Teorema McCreight-Meyer Union (Teorema 5.5 dari McCreight and Meyer, 1969 , versi gratis di sini ) akibat dari yang saya yakini disebabkan oleh Manuel Blum , ada fungsi tunggal $f$ sehingga $\mathsf{P} = \mathsf{DTIME}(f(n))$ . Fungsi ini tentu superpolinomial, tetapi "hanya nyaris."

Teorema ini berlaku lebih umum untuk setiap ukuran kompleksitas Blum $\Phi$ dan kelas serikat apa pun $\bigcup_{f \in S} \mathsf{BLUM}_{\Phi}(f(n))$ mana $S$ adalah ce, self-bound set of total fungsi yang dapat dihitung. (Serangkaian fungsi $S$ adalah ce jika ada fungsi parsial tunggal yang dapat dihitung $F(i,\vec{x})$ sedemikian sehingga $S = \{f_i(\vec{x}) | i \in \mathbb{N}\}$ mana $f_i(\vec{x}) := F(i,\vec{x})$ . Self-bounded berarti bahwa untuk setiap subset hingga $S_0 \subset S$ , ada fungsi dalam $S$ yang mendominasi semua $g \in S_0$ hampir di mana-mana. " $\mathsf{BLUM}_{\Phi}$"Adalah notasi yang belum pernah saya lihat sebelumnya, tetapi saya menyukainya :) - Saya menggunakannya untuk analog -terikat dari kelas kompleksitas terikat waktu.)$\Phi$