Бюрократы, editor, Администраторы
422
правки
Изменения
Нет описания правки
Для любого языка <tex>L \in \Sigma_1</tex> и соответствующего ему (из определения <tex>\Sigma_1</tex>) отношения <tex>R</tex> существует «оптимальная» (работающая «не сильно дольше», чем любая другая) программа <tex>p</tex>, сопоставляющая словам из <tex>L</tex> их сертификаты, то есть:
# <tex>x \in L \Leftrightarrow R(x, p(x)) = 1</tex>;
# для любой другой программы <tex>q</tex>, для которой верно <tex>x \in L \Leftrightarrow R(x, q(x)) = 1</tex>, найдутся такие константа <tex>c</tex> и полином <tex>r</tex>, что для любого <tex>\forall x \Rightarrow </tex> выполняется: <tex>T(p, x) \le c \cdot T(q, x) + r(|x|)</tex>.
|proof=
Построим «оптимальную» программу <tex>p(x)</tex>.
