Бюрократы, editor, Администраторы
422
правки
Изменения
Отмена правки 23418 участника Kirelagin (обсуждение)
Если выполнены все три свойства, то <tex>L \in \mathrm{NP} \setminus (\mathrm{P} \cup \mathrm{NPC})</tex>.
Пусть <tex>M_1, \ldots, M_n, \ldots</tex> — все такие машины Тьюринга из <tex>\tilde{\mathrm{P}}</tex>, что причём <tex>T(M_i, x) \le |x|^i</tex> для любого <tex>x \in \Sigma^*</tex>.
Пусть <tex>f_1, \ldots, f_n, \ldots</tex> — аналогичное множество полиномиальных функций: <tex>T(f_i, x) \le |x|^i</tex> для любого <tex>x \in \Sigma^*</tex>.
