Czy P jest równe przecięciu wszystkich wielobiegunowych klas czasowych?

Nazwijmy funkcję wielobiegunową, jeśli dla każdego c> 0 .$f(n)$ c > $\lim_{n\rightarrow\infty} n^c/f(n)=0$$c>0$

Oczywiste jest, że dla każdego języka $L\in {\mathsf P}$ utrzymuje, że $L\in {\mathsf {DTIME}}(f(n))$ dla każdego superminomalnego ograniczenia czasowego $f(n)$ . Zastanawiam się, czy odwrotność tego stwierdzenia jest również prawdą? To znaczy, jeśli znamy $L\in {\mathsf {DTIME}}(f(n))$ dla każdego superminomialnego ograniczenia czasowego $f(n)$ , czy oznacza to $L\in {\mathsf P}$ ? Innymi słowy, czy prawdą jest, że

Tak.

W rzeczywistości, przez McCreight-Meyer Unii twierdzenia (twierdzenie 5.5 McCreight i Meyer, 1969 , darmowa wersja tutaj ) to wynik, który moim zdaniem jest spowodowane Manuel Blum , istnieje pojedyncza funkcja taka, że . Ta funkcja jest z konieczności wielobiegunowa, ale „ledwo”.P = D T I M E ( f ( n ) $f$$\mathsf{P} = \mathsf{DTIME}(f(n))$

Twierdzenie to stosuje się bardziej ogólnie do każdej miary złożoności Bluma i każdej klasy unii gdzie jest ce, zbiorem własnym całkowite funkcje obliczalne. (Zestaw funkcji występuje, jeśli istnieje jedna częściowa funkcja obliczeniowa taka, że gdzie . Ograniczenie własne oznacza, że ​​dla każdego skończonego podzbioru istnieje funkcja w która dominuje nad wszystkimi prawie wszędzie. "$\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$B L U M $g \in S_0$$\mathsf{BLUM}_{\Phi}$"to notacja, której wcześniej nie widziałem, ale mi się podoba :) - używam jej do analogu związanego z klasą złożoności ograniczoną czasowo.)$\Phi$