Изменения

Пронумеруем все программы <tex>\lbrace p_i \rbrace_{i=1}^\infty</tex>. Поместим их в различные потоки, подадим на вход слово <tex>x</tex> и будем исполнять по одной инструкции в следующем порядке: на шаге с номером <tex>j</tex> запустим программу <tex>p_k</tex>, где <tex>k</tex> таково, что <tex>j</tex> делится на <tex>2^{k-1}</tex> и не делится на <tex>2^{k}</tex>. Таким образом, программа <tex>p_k</tex> будет исполняться на каждом <tex>2^k</tex>-м шаге начиная с <tex>k</tex>-того. Следовательно, если <tex>p_k</tex> завершит работу за <tex>T(p_k, x)</tex> инструкций, то к этому времени нами будет сделано <tex>k + (T(P_k, x) - 1) \cdot 2^k</tex> шагов.

Таким образом, если некоторая программа <tex>p_k</tex> генерирует верные сертификаты, то наша программа <tex>p</tex> завершит работу не более, чем за <tex>k + (T(p_k,x) + T(R, \langle x,p_k(x) \rangle)- 1) \cdot 2^k</tex> шагов. <tex>R \in P</tex> и <tex>|y| \le poly(|x|)</tex> из определения <tex>\Sigma_1</tex>, значит это равно <tex>k + (T(p_k,x) + poly(|x|)) \cdot 2^k = 2^k \cdot T(p_k,x) + poly(|x|)</tex>.