Бюрократы, editor, Администраторы
422
правки
Изменения
Нет описания правки
Как только <tex>p_k</tex>, выдав некоторое значение, завершит работу, запустим в том же потоке проверку сертификата слова <tex>x</tex>, используя вывод <tex>p_k</tex> в качестве сертификата. Если результат проверки положителен, искомый сертификат найден, иначе — продолжим работу больше ничего не запуская в этом потоке.
Таким образом, если некоторая программа <tex>p_kq = p_m</tex> генерирует верные сертификаты, то наша программа <tex>p</tex> завершит работу не более, чем за <tex>2^{km-1} + (T(p_kp_m,x) + T(R, \langle x,p_kp_m(x) \rangle) - 1) \cdot 2^km</tex> шагов. <tex>R \in P</tex> и <tex>|y| \le poly(|x|)</tex> из определения <tex>\Sigma_1</tex>, значит это равно <tex>2^{km-1} + (T(p_kp_m,x) + poly(|x|)) \cdot 2^k m = 2^k m \cdot T(p_kq,x) + poly(|x|)</tex>.
}}
