Р равняется пересечению всех суперполиномиальных временных классов?

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

Ясно, что для любого языка справедливо, что для каждого суперполиномиального ограничения по времени . Интересно, верно ли и обратное утверждение этого утверждения? То есть, если мы знаем для каждого суперполиномиального ограничения по времени , подразумевает ли это ? Другими словами, верно ли, что где пересечение берется по каждому суперполиному . L ∈ D T I M E ( f ( n ) ) f ( n ) L ∈ D T I M E ( f ( n ) $L\in {\mathsf P}$$L\in {\mathsf {DTIME}}(f(n))$$f(n)$$L\in {\mathsf {DTIME}}(f(n))$L ∈ P P = ∩ f D T I M E ( f ( n ) ) f ( n $f(n)$$L\in {\mathsf P}$

Да.

Фактически, согласно теореме Мак-Крейта-Мейера (теорема 5.5 Мак-Крейта и Мейера, 1969 , свободная версия здесь ) результат, который, как я полагаю, связан с Мануэлем Блумом , содержит одну функцию такую, что . Эта функция обязательно является суперполиномиальной, но «едва ли».P = D T I M E ( f ( n ) $f$$\mathsf{P} = \mathsf{DTIME}(f(n))$

Эта теорема в более общем случае применима к любой мере сложности Блюма и к любому классу объединения где - ce, самоограниченное множество Всего вычислимых функций. (Набор функций равен ce, если существует одна частичная вычислимая функция такая, что , где Само-ограниченные средства , что для любого конечного подмножества. , есть функция в , которая доминирует все почти везде. "⋃ f ∈ S B L U M Φ ( f ( n ) ) S S F ( i , → x ) S = { f i ( → x ) | i ∈ N } f i ( → x ) : = F ( i , → x ) S 0 ⊂ S S g $\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}$«это нотация, которую я раньше не видел, но она мне нравится :) - я использую ее для ограниченного аналога класса сложности с ограничением по времени.)$\Phi$