Бюрократы, editor, Администраторы
422
правки
Изменения
Нет описания правки
Если выполнены все три свойства, то <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>.
